

![0_image_0.png](0_image_0.png)

1 2 3 4 5 6 7 8 9 10 11 1 2

prerequisite-free normal
13

prerequisite-free normal unary 14 prerequisite-free positive normal unary

| class of default theories       | form of defaults   |
|---------------------------------|--------------------|
| disjunction-free                |                    |
| unary                           |                    |
| disjunction-free ordered        |                    |
| ordered unary                   |                    |
| disjunction-free normal         |                    |
| Horn                            |                    |
| normal unary                    |                    |
| prerequisite-free               |                    |
| prerequisite-free ordered       |                    |
| prerequisite-free unary         |                    |
| prerequisite-free ordered unary |                    |
| prerequisite-free normal        |                    |

the restriction to normal defaults (Gottlob, 1992). We show that the complement of the problem is in Σ 2 , which directly implies that the problem is in Π 2 . The complementary problem is the existence of a P -preferred B extension   such that   /   . The guessing of a strict total order T that generates an extension   such that   /
can be done by a nondeterministic Turing machine in a polynomial number of steps: guess T , and guess the conclusions of generating defaults of  . The verification that    fulfills Brewka's definition takes a polynomial number of steps with an NP oracle for propositional satisfiability.

Theorem 4.7 Testing ∆ = BH    for default theories ∆ , strict partial orders P and formulae is Π 2 -complete.

Proof: Like the proof of the previous theorem except that no strict total orders need to be guessed.

□

## 4.2 Complexity In Syntactically Restricted Cases

In this section we investigate the complexity of the prioritized default logics in syntactically restricted cases. This subject is related to the research on the boundary between tractability and intractability of default logic without priorities by Kautz and Selman (1991) and Stillman (1990). First we analyze the case in which the priorities are strict total orders. Then we complete the complexity analysis by extending the results to arbitrary strict partial orders.

Kautz and Selman analyze the complexity of determining the existence of extensions, cautious reasoning, and brave reasoning for default theories with defaults of the form listed in Table 1 (excluding the prerequisite-free classes) and with objective parts that are sets of literals. In Table 1, the letters possibly subscripted   denote literals, and the