Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic

Details Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic

2006-03-05

arxiv.org/abs/cs/0603019v1

Computer Science

Logic in Computer Science

6 pages

Scientific paper

There has been a great of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the validity problem for all logics between K, T, and S4 is {\sl PSPACE}-complete, while for S5 it is {\sl NP}-complete. We show that, in a precise sense, it is \emph{negative introspection}, the axiom $\neg K p \rimp K \neg K p$, that causes the gap. In a precise sense, if we require this axiom, then the satisfiability problem is {\sl NP}-complete; without it, it is {\sl PSPACE}-complete.

Affiliated with

Also associated with

No associations

Rating

Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44423