Nonmonotonic reasoning is sometimes simpler

Grigori Schwarz, Mirostaw Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

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 premises is Σ2 P-complete. Similarly, we show that for a given formula ϕ and a set A of premises, it is Σ2 P-complete to decide whether ϕ belongs to at least one S4-expansion for A, and it is Π2 P-complete to decide whether ϕ belongs to all S4-expansions for A. 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 nonmonotoific formalism which is computationally easier than the monotonic logic that underlies it (assuming PSPACE does not collapse to Σ2 P).

Original languageEnglish
Title of host publicationComputational Logic and Proof Theory - 3rd Kurt Godel Colloquium, KGC 1993, Proceedings
EditorsGeorg Gottlob, Alexander Leitsch, Daniele Mundici
Pages313-324
Number of pages12
DOIs
StatePublished - 1993
Event3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993 - Brno, Czech Republic
Duration: Aug 24 1993Aug 27 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume713 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd Kurt Godel Colloquium on Computational Logic and Proof Theory, KGC 1993
Country/TerritoryCzech Republic
CityBrno
Period8/24/938/27/93

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this