Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic |
| |
Authors: | Halpern Joseph Y; Rego Leandro Chaves |
| |
Affiliation: | Computer Science Department, Cornell University, USA. E-mail: halpern{at}cs.cornell.edu |
| |
Abstract: | There has been a great deal of work on characterizing the complexityof the satisfiability and validity problem for modal logics.In particular, Ladner showed that the satisfiability problemfor all logics between K and S4 is PSPACE-hard, while for S5it is NP-complete. We show that it is negative introspection,the axiom ¬Kp K¬Kp, that causes the gap: if we addthis axiom to any modal logic between K and S4, then the satisfiabilityproblem becomes NP-complete. Indeed, the satisfiability problemis NP-complete for any modal logic that includes the negativeintrospection axiom. |
| |
Keywords: | Euclidean Property Negative Introspection K5 S5 PSPACE NP Knowledge Representation |
本文献已被 Oxford 等数据库收录! |
|