
3.4 Complexity Results 59
enable the use of a domain-specific planning algorithm) or given as part of the
input.
3.4 Complexity Results
As summarized in Table 3.2, the computational complexity for classical planning
problems (and thus for most set-theoretic and state-variable planning problems)
Table 3.2 Complexity of classical planning.
How the Allow Allow Complexity Complexity
Kind of operators negative negative of plan- of plan-
representation are given effects? preconditions? existence length
Yes Yes/no expspace- nexptime-
Classical complete complete
rep. In the Yes nexptime- nexptime-
input complete complete
No No exptime- nexptime-
complete complete