Planning systems are usually evaluated empirically, by letting them solve a suite of benchmark tasks. While such experiments are suitable for gathering information about the relative performance of planning systems, they do not allow drawing conclusions about their absolute performance. For such purposes, theoretical results such as those offered by complexity theory are required.
However, the body of existing work on the complexity of finding solutions in the classical planning benchmark domains is sparse. In this talk, we discuss some new complexity results for the planning domains introduced in the 2002 and 2004 planning competitions and analyze the complexity of finding good quality plans in those planning domains where finding some plan is easy, yet finding an optimal plan is hard.