---
title: "Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic"
authors:
  - "Joseph Y. Halpern"
  - "Leandro Chaves Rêgo"
doi: ""
url: "https://ijcai.org/proceedings/2007/371"
pdf: "https://ijcai.org/proceedings/2007/0371.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2306-2310"
track: ""
keywords:
---

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

Joseph Y. Halpern, Leandro Chaves Rêgo

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2306-2310.

## Abstract

There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all logics between K and S4 is PSPACE-hard, while for S5, it is NP-complete. We show that it is negative introspection axiom that causes the gap: if we add this axiom to any modal logic between K and S4, then the satisfiability problem becomes NP-complete. Indeed, the satisfiability problem is NP-complete for any modal logic that includes the negative introspection axiom.