@article{ladner:467,
	title = {The Computational Complexity of Provability in Systems of Modal Propositional
	Logic},
	author = {Richard E. Ladner},
	journal = {SIAM Journal on Computing},
	number = {3},
	pages = {467-480},
	publisher = {SIAM},
	url = {http://link.aip.org/link/?SMJ/6/467/1},
	volume = {6},
	year = {1977},
	biburl = {http://www.bibsonomy.org/bibtex/2d09e045df5e654724aa4c8ea52e76751/ramaz},
	abstract = {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.},
	doi = {10.1137/0206033},
	keywords = {complexity computational logic; modal }
}