Time-Inconsistent Planning: Simple Motivation Is Hard to Find
Authors: Fedor V. Fomin, Torstein J. F. Strømme9843-9850
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove two main results about the complexity of SIMPLE MOTIVATING SUBGRAPH. First, we show that the problem is solvable in linear time when k = 0, and is NP-complete otherwise. Secondly, we show that when the costs are bounded by some polynomial in the size of the task graph, then it is solvable in polynomial time for every fixed k. More precisely, we show the following. Theorem 3. SIMPLE MOTIVATING SUBGRAPH is solvable in polynomial time for k = 0, and is NP-complete for any k 1. Theorem 4. SIMPLE MOTIVATING SUBGRAPH is solvable in time (|V (G)| W)O(k) whenever all edge weights are integers and W is the sum of all weights. Theorem 5. Unless FPT = W[1], there is no algorithm solving SIMPLE MOTIVATING SUBGRAPH in time (|V (G)| W)O(1) f(k) for any function f of k only. |
| Researcher Affiliation | Academia | Fedor V. Fomin,1 Torstein J. F. Strømme1 1University of Bergen, Norway |
| Pseudocode | Yes | Algorithm 6: MOTIVATING PATH Algorithm 9: Reduction from SUBSET SUM to SIMPLE MOTIVATING SUBGRAPH (k = 1) |
| Open Source Code | No | The paper does not provide any statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | This is a theoretical paper. It does not describe any experiments involving training data or publicly available datasets. |
| Dataset Splits | No | This is a theoretical paper. It does not involve any empirical validation or dataset splits. |
| Hardware Specification | No | This is a theoretical paper focusing on computational complexity and algorithms. No hardware specifications are mentioned for running experiments. |
| Software Dependencies | No | This is a theoretical paper. It does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper. It does not describe any experimental setup details such as hyperparameters or training settings. |