Algorithms and conditional lower bounds for planning problems
From MaRDI portal
Recommendations
- Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
- Conditionally Optimal Algorithms for Generalized B\"uchi Games
- The complexity of planning problems with simple causal graphs
- Upper and lower time and space bounds for planning
- Time and Space Bounds for Planning
Cites work
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- A new algorithm for optimal 2-constraint satisfaction and its implications
- AND/OR graph heuristic search methods
- Depth-First Search and Linear Graph Algorithms
- Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
- Graph expansion and communication costs of fast matrix multiplication
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 2000828 (Why is no real title available?)
- scientific article; zbMATH DE number 2238822 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
- Multiplying matrices faster than coppersmith-winograd
- Near-linear time algorithms for Streett objectives in graphs and MDPs
- Number of quantifiers is better than number of tape cells
- On some fine-grained questions in algorithms and complexity
- On the menbership problem for functional and multivalued dependencies in relational databases
- Plan aggregation for strong cyclic planning in nondeterministic domains
- Planning Algorithms
- Planning and acting in partially observable stochastic domains
- Powers of tensors and fast matrix multiplication
- Refining complexity analyses in planning by exploiting the exponential time hypothesis
- Subcubic equivalences between path, matrix, and triangle problems
- The Complexity of Markov Decision Processes
- The computational complexity of propositional STRIPS planning
- Tight hardness for shortest cycles and paths in sparse graphs
- Time and Space Bounds for Planning
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Weak, strong, and strong cyclic planning via symbolic model checking
Cited in
(8)- State-variable planning under structural restrictions: algorithms and complexity
- Sufficient Conditions for the Existence of Resolution Complete Planning Algorithms
- FROM PLANNING TO SEARCHING FOR THE SHORTEST PLAN: AN OPTIMAL TRANSITION
- scientific article; zbMATH DE number 6519681 (Why is no real title available?)
- Time and Space Bounds for Planning
- Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
- Fine-grained complexity lower bounds for problems in computer aided verification
- Graph planning with expected finite horizon
This page was built for publication: Algorithms and conditional lower bounds for planning problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2238604)
