THE COMPLEXITY OF DEFAULT REASONING UNDER THE STATIONARY FIXED-POINT SEMANTICS

Stationany default extensions have recently been introduced by Przymusinska and Przymusinsky as an interesting alternative to classical extensions in Reiter's default logic. An important property of this new approach is that the set of all stationary extensions has a unique minimal element. In this paper we investigate the computational complexity of the main reasoning tasks in propositional stationary default logic, namely, cautious and brave reasoning. We show that cautious reasoning is complete for Delta(2)(P) while brave reasoning is Sigma(2)(P)-complete. We also show that for normal default theories, the least fixed point iteration used to compute the unique minimal stationary extension is noticeably simplified. Based on this observation we show that cautious reasoning with normal defaults is complete for p(NP[log n]). This is the class of decision problems solvable in polynomial time with a logarithmic number of queries to an oracle in NP. (C) 1995 Academic Press. Inc.