Complexity results for logics of local reasoning and inconsistent belief
Martin W. Allen · 2005
Fagin, Halpern, Moses, and Vardi have proposed a framework of epistemic agents with multiple "frames of mind" (local-reasoning structures), to solve problems concerning inconsistent knowledge and logical omniscience. We investigate a class of related modal logics. These logics replace the usual closure under full conjunction for the # operator with progressively weaker versions, and comprise a hierarchy with the traditional modal logic K at the top, and an infinite number of logics ordered by inclusion under it, all strictly stronger than N , the weakest monotonic modal logic. Previous results have used N to represent local-reasoning structures. Our result shows that there are stronger logics applicable to such structures, suggesting that stronger forms of inference can be used to represent imperfect knowledge-based agents and protocols. Further, it is shown that the satisfiability question for each of these logics is PSPACE-complete, strictly harder than for N . This also answers a conjecture of Vardi: the border between NP- and PSPACE-hardness in modal-logical satisfiability problems is associated with conjunctive closure, however weak.