setting the problem is to define what are the correct inferences in the presence of priorities. There have been many proposals of differing generality. Preferred subtheories (Brewka, 1989) and ordered theory presentations (Ryan, 1992) do not have as general a notion of defaults as Reiter's default logic, and they can both be translated to prerequisite-free normal default theories of a prioritized default logic (Rintanen, 1999). Also the definitions of model minimization in conditional entailment (Geffner & Pearl, 1992) and in prioritized circumscription (Lifschitz, 1985) do not directly support defaults with prerequisites.

In this work we concentrate on Brewka's (1994) and Baader and Hollunder's (1995)
proposals for incorporating priorities to default logic, as well as a proposal that uses lexicographic comparison (Rintanen, 1999). These three proposals address default reasoning with defaults that have prerequisites. Like earlier work on complexity of nonmonotonic logics (Kautz & Selman, 1991; Stillman, 1990; Gottlob, 1992), the purpose of our investigation is to point out fundamental differences and similarities between these logics, characterized by polynomial time translatability between their decision problems, and to identify restricted classes of default theories where reasoning is tractable. The first kind of results are useful for example when developing theorem-proving techniques for the logics in question. The inexistence of polynomial time translations between two decision problems indicates that the techniques needed are likely to be different: it is not feasible to solve one decision problem by simply translating it to the other. Also, if polynomial time translations exist and they turn out to be simple, there is often no reason to treat the decision problems separately. The second kind of results, identification of tractable cases, directly give efficient, that is polynomial time, decision procedures for prioritized reasoning in special cases. The utility of these algorithms depends on the application at hand. In many cases the restrictions that lead to polynomial time decision procedures are too severe to make the procedures practically useful. Even though nonmonotonic reasoning usually cannot be performed in polynomial time, new developments in implementation techniques have made it possible to solve problems that previously were too difficult (Niemela & Simons, 1996). Hence there are some prospects of making nonmonotonic reasoning practically useful, which makes the problem of introducing priority information in nonmonotonic reasoning more acute.  This paper can be seen as giving guidelines in that direction.

The decision problems of propositional default logic are located on the second level of the polynomial hierarchy (Gottlob, 1992), and hence they do not belong to the classes NP
or co-NP unless the polynomial hierarchy collapses to its first level. The proof of this result suggests that reasoning in default logic cannot be performed in polynomial time simply by restricting the formulae in default theories to a tractable subclass of propositional logic like 2-literal clauses (Even, Itai, & Shamir, 1976) or Horn clauses (Dowling & Gallier, 1984). This fact can be seen as a consequence of the possibility of conflicting defaults. A conflict between defaults gives rise to multiple extensions because a case analysis on alternative ways of resolving the conflict is required.  For a default theory of size  , the number of conflicts may be proportional to   , and each conflict may double the number of extensions. Hence the number of extensions can be proportional to 2 n . Priorities in many cases uniquely determine how a conflict between defaults is resolved, and hence the case analyses that lead to an exponential number of extensions can be avoided.  This gives rise to the question whether priorities would in some cases produce a computational advantage in the sense that the decision problems could be solved more efficiently than in the unprioritized case.