I) computable in polynomial time using no resp. a Σ
P
ioracle. We say, abusing terminology, that a search problem A is in FP (resp. F∆P
i+1), if there is a partial (single-valued) function f ∈ FP
(resp. f ∈ F∆P
i+1) such that f(I) ∈ S(I) and f(I) is undefined iff S(I) = ∅. For example, computing a satisfying assignment for a propositional CNF (FSAT) and computing an optimal tour in the Traveling Salesperson Problem (TSP) are in F∆P
2 under this view, cf. (Papadimitriou, 1994).

A partial function f is polynomial-time reducible to another partial function g, if there are polynomial-time computable functions h1 and h2 such that f(I) = h2(I, g(h1(I))) for all I and g(h1(I)) is defined whenever f(I) is defined. Hardness and completeness are defined as usual.

## 4.2 Problem Setting

We will focus on the following questions:
Checking Well-Definedness: Decide whether a given action description is well-defined wrt. a given planning domain PD, resp. whether a given planning domain PD is well-defined.

Admissible Planning: Decide whether for planning problem P an admissible (optimistic/secure)
plan exists wrt. a given cost value c, and find such a plan.

Optimal Planning: Find an optimal (optimistic/secure) plan for a given planning problem.

Notice that (Eiter et al., 2003b) focused on deciding the existence of optimistic/secure plans, rather than on actually finding plans, and presented a detailed study of the complexity of this task under various restrictions for ground (propositional) planning problems. In this paper, we confine the discussion to the case of planning problems P = hPD, Q ? (l)i which look for polynomial length plans, i.e., problems where the plan length l is bounded by some polynomial in the size of the input.

We shall consider here mainly ground (propositional) planning, and assume that the planning domains are well-typed and that the unique model of the background knowledge can be computed in polynomial time. In the general case, by well-known complexity results on logic programming, cf. (Dantsin, Eiter, Gottlob, & Voronkov, 2001), already evaluating the background knowledge is EXPTIME-hard, and the problems are thus provably intractable. We recall the following results, which appear in (or directly follow from) previous work (Eiter et al., 2003b).

Proposition 4.1 Deciding, given a propositional planning problem P *and a sequence* P = hA1**, . . . ,** Ali *of action sets, (i) whether a given sequence* T = ht1**, . . . , t**li *is a legal trajectory witnessing that* P is an optimistic plan for P is feasible in polynomial time, and (ii) whether P *is a secure plan for* P is ΠP
2
-complete.

## 4.3 Results

We start by considering checking well-definedness. For this problem, it is interesting to investigate the non-ground case, assuming that the background knowledge is already evaluated. This way we can assess the intrinsic difficulty of this task obtaining the following result.

Theorem 4.2 (Complexity of checking well-definedness) Given a Kc *planning domain* PD =
hΠ,h**D, R**ii and the unique model M of Π, checking (i) well-definedness of a given action declaration d of form (1) wrt. PD and (ii) well-definedness of PD *are both* ΠP
2
-complete.