The Complexity of Reasoning with Boolean Modal Logics

摘要

In this paper, we investigate the complexity of reasoning with various Boolean Modal Logics. The main results are that (ⅰ) adding negation of modal parameters to (multi-modal) K makes reasoning ExpTime-complete and (ⅱ) adding atomic negation and conjunction to K even yields a NExpTime-complete logic. The last result is relativized by the fact that it depends on an infinite number of modal parameters to be available. If the number of modal parameters is bounded, full Boolean Modal Logic becomes ExpTime-complete.