BibSonomy publications for /user/ramaz/logic;Fri Nov 23 14:13:20 CET 2007SIAM Journal on Computing3467-480The Computational Complexity of Provability in Systems of Modal Propositional Logic61977logic; computational complexity modal The computational complexity of the provability problem in systems of modal propositional logic is investigated. Every problem computable in polynomial space is $\log $ space reducible to the provability problem in any modal system between $K$ and $S4$. In particular, the provability problem in $K$, $T$, and $S4$ are $\log $ space complete in polynomial space. The nonprovability problem in $S5$ is $\log $ space complete in nondeterministic polynomial time.