Nonmonotonic reasoning is sometimes simpler!

Grigori Schwarz; Miroslaw Truszczynski

doi:10.1093/logcom/6.2.295

Nonmonotonic reasoning is sometimes simpler!

Grigori Schwarz, Miroslaw Truszczynski

Computer Science

Research output: Contribution to journal › Article › peer-review

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

Original language	English
Pages (from-to)	295-308
Number of pages	14
Journal	Journal of Logic and Computation
Volume	6
Issue number	2
DOIs	https://doi.org/10.1093/logcom/6.2.295
State	Published - 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.

Keywords

Complexity
Expansions
Nonmonotonic logics
S
S4 F

ASJC Scopus subject areas

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

Access to Document

10.1093/logcom/6.2.295

Cite this

@article{bdd892b2c5be4b16bffa34208f01ace2,

title = "Nonmonotonic reasoning is sometimes simpler!",

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 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).",

keywords = "Complexity, Expansions, Nonmonotonic logics, S, S4 F",

author = "Grigori Schwarz and Miroslaw Truszczynski",

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.",

year = "1996",

month = apr,

doi = "10.1093/logcom/6.2.295",

language = "English",

volume = "6",

pages = "295--308",

number = "2",

}

TY - JOUR

T1 - Nonmonotonic reasoning is sometimes simpler!

AU - Schwarz, Grigori

AU - Truszczynski, Miroslaw

N1 - 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.

PY - 1996/4

Y1 - 1996/4

N2 - 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).

AB - 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).

KW - Complexity

KW - Expansions

KW - Nonmonotonic logics

KW - S

KW - S4 F

UR - http://www.scopus.com/inward/record.url?scp=0040241316&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040241316&partnerID=8YFLogxK

U2 - 10.1093/logcom/6.2.295

DO - 10.1093/logcom/6.2.295

M3 - Article

AN - SCOPUS:0040241316

SN - 0955-792X

VL - 6

SP - 295

EP - 308

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

IS - 2

ER -

Nonmonotonic reasoning is sometimes simpler!

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this