denote propositional variables. Stillman considers only the problem of brave letters reasoning, but considers a wider range of classes. He analyzes default theories the objective parts of which are sets of Horn clauses or sets of 2-literal clauses, and also the case where defaults are prerequisite-free. 1 The most general tractable classes in default logic without priorities are the following.

- If the objective part may contain Horn clauses, none of the restrictions on the form of default rules is sufficient for achieving tractability in brave reasoning (Stillman, 1990). Cautious reasoning has not been investigated.

- If consists of 2-literal clauses, brave reasoning for the prerequisite-free normal class is tractable (Stillman, 1990). Cautious reasoning has not been investigated.

- If consists of literals, brave reasoning for the prerequisite-free normal class and the Horn class are tractable (Kautz & Selman, 1991; Stillman, 1990).  Cautious reasoning is tractable for the normal unary class (Kautz & Selman, 1991). Cautious reasoning for the prerequisite-free classes has not been investigated.
We present a similar analysis for the same classes of prioritized default logics starting with the case where priorities totally order the defaults. We present for each class either a polynomial time decision procedure, or an NP-hardness or a co-NP-hardness result.

## 4.2.1 Summary

Because of the constructive nature of the definitions of preferred extensions in the prioritized default logics by Brewka and by Baader and Hollunder, constructing the unique preferred extensions of default theories with total priorities is tractable whenever the logical consequence tests in propositional logic are tractable (Theorem 4.8.) This is because there is always a unique default that is applied next, and this default cannot be defeated by any default applied later. So with total priorities, these prioritized default logics are computationally much easier than Reiter's default logic.

For unrestricted priorities, Table 2 summarizes the complexity of = B and = BH with various syntactic restrictions. As Brewka does not consider non-normal default theories, complexity results on seminormal classes concern the consequence relation = BH only. In cases where Reiter's default logic is tractable and a prioritized default logic is not, or vice versa, the complexity characterization is set in boldface.

Table 3 gives references to the theorems and corollaries where the results are stated.  We to indicate that the intractability of the class is directly implied by the use the notation intractability of the subclass in the same column, and the notation to indicate that the tractability is implied by the tractability of the superclass in the same column. When the complexity is directly implied by the complexity of an unprioritized class of default theories investigated by Kautz and Selman (1991) we indicate this by K&S.