-
Views
-
Cite
Cite
GRIGORI SCHWARZ, MIROSLAW TRUSZCZYNSKI, Nonmonotonic Reasoning is Sometimes Simpler!, Journal of Logic and Computation, Volume 6, Issue 2, April 1996, Pages 295–308, https://doi.org/10.1093/logcom/6.2.295
Close - Share Icon Share
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 ΣP2-complete. Similarly, we show that for a given formula Φ and a set A of premisses, it is ΣP2-complete to decide whether Φ belongs to at least one S4-expansion for A, and it is πP2-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 ΣP2).
