# Complexity Of Prioritized Default Logics

## Jussi Rintanen

RINTANEN@INFORMATIK. UNI-ULM.DE
Universitat Ulm Fakultat für Informatik Albert-Einstein-Allee 89069 Ulm, GERMANY

## Abstract

In default reasoning, usually not all possible ways of resolving conflicts between default rules are acceptable.  Criteria expressing acceptable ways of resolving the conflicts may be hardwired in the inference mechanism, for example specificity in inheritance reasoning can be handled this way, or they may be given abstractly as an ordering on the default rules. In this article we investigate formalizations of the latter approach in Reiter's default logic.  Our goal is to analyze and compare the computational properties of three such formalizations in terms of their computational complexity: the prioritized default logics of Baader and Hollunder, and Brewka, and a prioritized default logic that is based on lexicographic comparison. The analysis locates the propositional variants of these logics on the second and third levels of the polynomial hierarchy, and identifies the boundary between tractable and intractable inference for restricted classes of prioritized default theories.

## 1. Introduction

Nonmonotonic logics and related systems for nonmonotonic and default reasoning (Reiter, 1980; Moore, 1985; McCarthy, 1980) were developed for representing knowledge and forms of reasoning that are not conveniently expressible in monotonic logics, like the first-order predicate logic or propositional logics. In nonmonotonic logics inferences can be made on the basis of what cannot be inferred from a set of facts.  When extending this set, some of the inferences may become invalid, and hence the set of inferable facts does not monotonically increase. For example, in the kind of reasoning expressed as inheritance networks (Horty, 1994), one network link may say that priests imbibe non-alcoholic beverages only. This is, in the absence of contrary information, a sufficient reason to conclude that a certain priest will not drink vodka.  Without contradiction, information stating that the priest does drink vodka can be added, which retracts the previous conclusion.

The need to incorporate priority information to nonmonotonic logics (Lifschitz, 1985; Brewka, 1989; Geffner & Pearl, 1992; Ryan, 1992; Brewka, 1994; Baader & Hollunder, 1995) stems from the possibility that two default rules are in conflict. One source of such priority information is the specificity of defaults. When one rule says that priests usually do not drink and another says that men usually do, inferences concerning male priests should be based on the first one because it is more specific, as male priests are a small subset of men. Specificity as a basis for resolving conflicts between defaults has been investigated in the framework of path-based inheritance theories (Horty, 1994). In general, however, priorities may come from different sources, and therefore it is justified to investigate nonmonotonic reasoning with an abstract notion of priorities as orderings on defaults. In this