## 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 Σ_{2}^{P}-complete. Similarly, we show that for a given formula φ and a set A of premisses, it is Σ_{2}^{P}-complete to decide whether φ belongs to at least one S4-expansion for A, and it is II_{2}^{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 Σ_{2}^{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 | |

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