initially : total hasLamp(X).

caused false if -hasLamp(joe), -hasLamp(jack),
-hasLamp(william), -hasLamp(averell).

The first statement says that each person either has a lamp or not, and the second that at least one of them must have a lamp. For a detailed discussion on the use of the "total" statement for modeling incomplete knowledge and non-determinism we refer to (Eiter et al., 2003b).

As we can easily see, an optimal secure solution will take at least 17 minutes, since the original case (where only joe has a lamp) is one of the possible initial situations, for which the cost of an optimistic plan which is optimal over all plan lengths was 17. However, a secure plan which is optimal over all plan lengths requires at least 8 steps now (but no higher cost): Different from optimistic plans, we need one extra step at the beginning which makes sure that one of those who walk first (above, joe and jack) has the lamp, which is effected by the proper takeLamp action.

An example of such a plan is the following which has cost 17:
P = h {takeLamp(joe)}, {crossTogether(joe, jack)}, {cross(joe)},
{takeLamp(william)}, {crossTogether(william, averell)}, {takeLamp(jack)},
{cross(jack)}, {crossTogether(joe, jack)} i We can easily check that P works for every possible initial situation. Thus, it is an optimal (secure)
plan for plan length 8, and moreover also for arbitrary plan length.

## 4. Computational Complexity

In this section, we will address the computational complexity of Kc, complementing similar results for the language K (Eiter et al., 2003b).

## 4.1 Complexity Classes

We assume that the reader is familiar with the basic notions of complexity theory, such as P, NP,
problem reductions and completeness; see e.g. (Papadimitriou, 1994) and references therein. We recall that the Polynomial Hierarchy (PH) contains the classes Σ
P
0 = ΠP
0 = ∆P
0 = P and Σ
P
i+1 =
NPΣP
i , ΠP
i+1 = co-Σ
P
i+1, ∆P
i+1 = PΣP
i , for i ≥ 0. In particular, Σ
P
1 **= NP** and ∆P
2 = PNP.

Note that these classes contain decision problems (i.e., problems where the answer is "yes" or "no"). While checking well-definedness and deciding plan existence are such problems, computing a plan is a *search problem*, where for each problem instance I a (possibly empty) finite set S(I) of solutions exists. To solve such a problem, a (possibly nondeterministic) algorithm must compute the alternative solutions from this set in its computation branches, if S(I) is not empty. More precisely, search problems are solved by transducers, i.e., Turing machines equipped with an output tape. If the machine halts in an accepting state, then the contents of the output tape is the result of the computation. Observe that a nondeterministic machine computes a (partial) multi-valued function.

As an analog to NP, the class **NPMV** contains those search problems where S(I) can be computed by a nondeterministic Turing machine in polynomial time; for a precise definition, see (Selman, 1994). In analogy to Σ
P
i+1, by Σ
P
i+1**MV = NPMV**ΣP
i , i ≥ 0, we denote the generalization of NPMV where the machine has access to a Σ
P
ioracle.

Analogs to the classes P and ∆P
i+1, i ≥ 0, are given by the classes FP and F∆P
i+1, i ≥ 0, which contain the partial single-valued functions (that is, |S(I)| ≤ 1 for each problem instance