Computational Logic SeminarTuesday, March 4, 20141:00 pmnote new timeGraduate Center, rm. 8405New room, for this talk only!

# Parameters and the Complexity of Modal Satisfiability

## Antonis Achilleos

### Graduate Center CUNY

The complexity of Modal Logic has been extensively studied. Ladner has established most of what are now considered classical results on the matter, determining that most of the usual modal logics are PSPACE-complete. Furthermore, as Chagrov and Rybakov showed, some of these logics remain PSPACE-complete even for their variable-free fragments. We present parameters of modal formulas whose effect on the complexity of modal logic has been studied – like modal depth – and we identify sources of complexity for modal satisfiability.

A big part of this talk is joint work with Michael Lampis and Valia Mitsou.

Posted by

on March 2nd, 2014