translations between the decision problems of these two formalizations exist.  There are also polynomial time translations to and from Reiter's default logic. The third formalization, that uses lexicographic comparison to select the preferred extensions, is not reducible to Reiter's default logic in polynomial time (under the standard complexity-theoretic assumptions.)
An analysis of the complexity of the decision problems in syntactically restricted cases, following earlier work by Kautz and Selman (1991) and Stillman (1990), identifies the effect of priorities on the boundary between tractability and intractability in the prioritized versions of the decision problems. With priorities that totally order the defaults and classical propositional reasoning that is tractable, for example with Horn clauses or 2-literal clauses, reasoning in Brewka's and in Baader and Hollunder's logics is polynomial time. For the formalization of prioritized default reasoning that uses lexicographic comparison, the same assumptions yield tractable reasoning only for the so-called Horn defaults and background theories without disjunction, as well as normal defaults without prerequisites and disjunction. When arbitrary priorities are allowed, in all three logics reasoning is tractable only when defaults are of the form :
for literals and the background theories are sets of literals.

## Acknow Ledgements

This research was mainly carried out at the Helsinki University of Technology and finished at the University of Ulm while funded by the SFB 527 of the Deutsche Forschungsgemeinschaft. We gratefully acknowledge the generous support of the Finnish Cultural Foundation and the Finnish Academy of Science and Letters that helped completing this work.

We thank the four anonymous reviewers for pointing out some errors and for advice on restructuring the article and on including references to related work in Section 6. Holger Pfeifer provided valuable assistance in proof-reading.

## References

Baader, F., & Hollunder, B. (1995). Priorities on defaults with prerequisites, and their application in treating specificity in terminological default logic. Journal of Automated Reasoning, 15 (1), 41–68.

Balcázar, J. L., Díaz, I., & Gabarró, J. (1995). Structural Complexity I. Springer-Verlag, Berlin.

Ben-Eliyahu, R., & Dechter, R. (1996). Default reasoning using classical logic. Artificial Intelligence, 84 (1-2), 113 150.

Brewka, G. (1989). Preferred subtheories: an extended logical framework for default reasoning. In Proceedings of the 11th International Joint Conference on Artificial Intelligence, pp. 1043 1048 Detroit. Morgan Kaufmann Publishers.

Brewka, G. (1994). Adding priorities and specificity to default logic. In MacNish, C., Pearce, D., & Moniz Pereira, L. (Eds.), Logic in Artificial Intelligence: Proceedings of the 4th