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

Stationany default extensions have recently been introduced by Przymus inska and Przymusinsky as an interesting alternative to classical exte nsions in Reiter's default logic. An important property of this new ap proach is that the set of all stationary extensions has a unique minim al 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)-comp lete. We also show that for normal default theories, the least fixed p oint iteration used to compute the unique minimal stationary extension is noticeably simplified. Based on this observation we show that caut ious 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 Pr ess. Inc.