Nonmonotonic reasoning is sometimes simpler!

Grigori Schwarz, Miroslaw Truszczynski

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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 Σ2P-complete. Similarly, we show that for a given formula φ and a set A of premisses, it is Σ2P-complete to decide whether φ belongs to at least one S4-expansion for A, and it is II2P-complete to decide whether φ 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 Σ2P).

Original languageEnglish
Pages (from-to)295-308
Number of pages14
JournalJournal of Logic and Computation
Issue number2
StatePublished - Apr 1996

Bibliographical note

Funding Information:
The authors gratefully acknowledge comments on earlier drafts of the paper from Georg Got-tlob, Thomas Eiter and Rajeev Gore. The comments of the anonymous referee were very useful and helped to improve the final look of the paper. The first author was supported by the National Science Foundation under grant IRI-9220645. The second author was partially supported by the National Science Foundation under grant IRI-9012902.


  • Complexity
  • Expansions
  • Nonmonotonic logics
  • S
  • S4 F

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Arts and Humanities (miscellaneous)
  • Hardware and Architecture
  • Logic


Dive into the research topics of 'Nonmonotonic reasoning is sometimes simpler!'. Together they form a unique fingerprint.

Cite this