Algorithms and conditional lower bounds for planning problems

DOI10.1016/j.artint.2021.103499OpenAlexW3138721759MaRDI QIDQ2238604

Wolfgang Dvořák, Krishnendu Chatterjee, Alexander Svozil, Monika R. Henzinger

Publication date: 2 November 2021

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.07031

zbMATH Keywords

probabilistic planninggraph gamesstrong exponential time hypothesisadversarial planningconditional lower bounds

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Related Items (1)

Fine-grained complexity lower bounds for problems in computer aided verification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planning and acting in partially observable stochastic domains
• Plan aggregation for strong cyclic planning in nondeterministic domains
• Refining complexity analyses in planning by exploiting the exponential time hypothesis
• Weak, strong, and strong cyclic planning via symbolic model checking
• Number of quantifiers is better than number of tape cells
• The computational complexity of propositional STRIPS planning
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
• Powers of tensors and fast matrix multiplication
• AND/OR graph heuristic search methods
• The Complexity of Markov Decision Processes
• On the menbership problem for functional and multivalued dependencies in relational databases
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
• Time and Space Bounds for Planning
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Model and Objective Separation with Conditional Lower Bounds
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Graph expansion and communication costs of fast matrix multiplication
• Multiplying matrices faster than coppersmith-winograd
• Planning Algorithms
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Algorithms and conditional lower bounds for planning problems