Refining complexity analyses in planning by exploiting the exponential time hypothesis

1. Bäckström, C., Jonsson, P.: All PSPACE-complete planning problems are equal but some are more equal than others. In: Proceedings 4th Annual Symposium on Combinatorial Search (SOCS-11), pp 10–17, Barcelona, Spain (2011)

2. Bäckström, C., Jonsson, P.: Algorithms and limits for compact plan representations. J. Artif. Intell. Res. 44, 141–177 (2012)

   MathSciNet  MATH  Google Scholar 

3. Bäckström, C., Jonsson, P.: A refined view of causal graphs and component sizes: SP-closed graph classes and beyond. J. Artif. Intell. Res. 47, 575–611 (2013)

   MathSciNet  MATH  Google Scholar 

4. Bäckström, C., Jonsson, P., Ordyniak, S., Szeider, S.: A complete parameterized complexity analysis of bounded planning. J. Comput. Syst. Sci., 1311–1332 (2015)

5. Bäckström, C., Jonsson, P., Ståhlberg, S.: Fast detection of unsolvable planning instances using local consistency. In: Proceedings 6th Annual Symposium on Combinatorial Search (SOCS-13), pp 29–37, WA, USA (2013)

6. Bäckström, C., Nebel, B.: Complexity results for SAS + planning. Comput. Intell. 11, 625–656 (1995)

   Article  MathSciNet  Google Scholar 

7. Bogomolov, S., Magazzeni, D., Podelski, A., Wehrle, M.: Planning as model checking in hybrid domains. In: Proceedings 28th AAAI Conference on Artificial Intelligence (AAAI-14), pp 2228–2234, QC, Canada (2014)

8. Bylander, T.: The computational complexity of propositional STRIPS planning. Artif. Intell. 69(1-2), 165–204 (1994)

   Article  MathSciNet  MATH  Google Scholar 

9. Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216–231 (2005)

   Article  MathSciNet  MATH  Google Scholar 

10. Chen, J., Huang, X., Kanj, I., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346–1367 (2006)

    Article  MathSciNet  MATH  Google Scholar 

11. Chen, Y., Grohe, M.: An isomorphism between subexponential and parameterized complexity theory. SIAM J. Comput. 37(4), 1228–1258 (2007)

    Article  MathSciNet  MATH  Google Scholar 

12. Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness (1979)

13. Helmert, M.: Complexity results for standard benchmark domains in planning. Artif. Intell. 143(2), 219–262 (2003)

    Article  MathSciNet  MATH  Google Scholar 

14. Hoffmann, J., Kissmann, P., Torralba, Á.: Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability. In: Proceedings 21st European Conference on Artificial Intelligence (ECAI-2014), pp 441–446 (2014)

15. Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)

    Article  MathSciNet  MATH  Google Scholar 

16. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512–530 (2001)

    Article  MathSciNet  MATH  Google Scholar 

17. Jonsson, P., Bäckström, C.: Tractable plan existence does not imply tractable plan generation. Ann. Math. Artif. Intell. 22(3-4), 281–296 (1998)

    Article  MathSciNet  MATH  Google Scholar 

18. Jonsson, P., Lagerkvist, V., Nordh, G., Zanuttini, B.: Complexity of SAT problems, clone theory and the exponential time hypothesis. In: Proceedings 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-13), pp 1264–1277, LA, USA (2013)

19. Kanj, I., Szeider, S.: On the subexponential time complexity of CSP. In: Proceedings 27th AAAI Conference on Artificial Intelligence (AAAI-13), pp 459–465, WA, USA (2013)

20. Levesque, H.: Logic and the complexity of reasoning. J. Philos. Log. 17(4), 355–389 (1988)

    Article  MathSciNet  Google Scholar 

21. Linares López, C., Celorrio, S.J., Olaya, A.G.: The deterministic part of the seventh international planning competition. Artif. Intell. 223, 82–119 (2015)

    Article  Google Scholar 

22. Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. B. EATCS 105, 41–72 (2011)

    MathSciNet  MATH  Google Scholar 

23. Marx, D.: On the optiMality of planar and geometric approximation schemes. In: Proceedings 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS-07), pp 338–348, RI, USA (2007)

24. Rintanen, J.: Generation of hard solvable planning problems. Technical report TR-CS-12-03, College of Engineering and Computer Science, The Australian National University, Canberra, Australia (2012)

25. Santhanam, R., Srinivasan, S.: On the limits of sparsification. In: Proceeding of the 39th International Colloquium on Automata, Languages, and Programming (ICALP-12), pp 774–785, Warwick, UK (2012)

26. Savitch, W.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177–192 (1970)

    Article  MathSciNet  MATH  Google Scholar 

27. Sipser, M.: Introduction to the theory of computation, 2nd edn. Thomson Course Technology (2006)

28. Stearns, R.E.: Turing award lecture: It’s time to reconsider time. Commun. ACM 37(11), 95–99 (1994)

    Article  Google Scholar 

29. Stearns, R.E.: Deterministic versus nondeterministic time and lower bound problems. J. ACM 50(1), 91–95 (2003)

    Article  MathSciNet  MATH  Google Scholar 

30. Stearns, R.E., Hunt, III, H.B.: Power indices and easier hard problems. Math. Syst. Theory 23(4), 209–225 (1990)

31. Traxler, P.: The time complexity of constraint satisfaction. In: Proceeding of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC-08), pp 190–201, BC, Canada (2008)

Download references