Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Time and Space Bounds for Planning
Authors: Christer Bäckström, Peter Jonsson
JAIR 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The abstract states: "We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time and thus require O(2cn) time for some c > 0. In many cases, we can even prove closely matching upper and lower bounds; for every ε > 0, the problem can be solved in time O(2(1+ε)n) but not in time O(2(1 ε)n). Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space." The paper is primarily concerned with theoretical complexity analysis, theorems, and proofs. |
| Researcher Affiliation | Academia | Both authors are affiliated with "Department of Computer and Information Science Linköping University", and their email addresses are "EMAIL" and "EMAIL", indicating an academic affiliation. |
| Pseudocode | Yes | The paper includes "Figure 1: Greedy algorithm for solving Psat(PSN + +)." on page 14, which presents a structured algorithm block. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to code repositories or mention code in supplementary materials for the methodologies described. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis of planning problems. It does not use or reference any specific datasets for empirical evaluation, nor does it provide access information for any data. |
| Dataset Splits | No | The paper does not involve empirical studies with datasets, therefore, there is no discussion of dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical complexity bounds and does not describe any experimental hardware used. |
| Software Dependencies | No | The paper does not describe any specific software dependencies with version numbers, as it is a theoretical work and does not detail an experimental setup. |
| Experiment Setup | No | The paper is theoretical in nature, presenting proofs, theorems, and complexity analyses rather than empirical experiments. Therefore, there are no details about experimental setup or hyperparameters. |