Volume 6: January - December 1996

Issue 2: April 1996


Nonmonotonic reasoning is sometimes simpler!

  • Nonmonotonic reasoning is sometimes simpler!
  • G. Schwarz1 and M. Truszczynski2 Robotics Laboratory, Computer Science Department, Stanford University, Stanford, CA 943-5-4110, USA and 2Computer Science Department, University of Kentucky, Lexington, KY 40506-0046, USA


    We establish the complexity of decision problems associated with the nonmonotonic modal logic S4. We prove that the problem of existence of an S4-expansion for a given set A of premisses is [Sigma]P2-complete. Similarly, we show that for a given formula [phi] and a set A of premisses, it is [Sigma]P2-complete to decide whether [phi] belongs to at least one S4-expansion for A, and it is IIP P2-compete to decide whether [phi] belongs to all S4-expansions for A. This refutes a conjecture of Gottlob that these problems are PSPACE-complete. An interesting aspect of these results is that reasoning (testing satisfiability and provability) in the monotonic modal logic S4 is PSPACE-complete. To the best of our knowledge, the nonmonotonic logic S4 is the first example of a nonmonotonic formalism which is computationally easier than the monotonic logic that underlies it (assuming PSPACE does not collapse to [Sigma]P2).

    Keywords: Nonmonotonic logics, expansions, S, S4 F, complexity.

    Pages: 295 - 308

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    Click here to register with OUP.

    This page is maintained by OUP admin

    Last updated 15 Jul 96

    Part of the OUP Journals World Wide Web service.

    Copyright Oxford University Press, 1996