Complexity results for logics of local reasoning and inconsistent belief
Martin Allen
Abstract
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
\square 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.
@InProceedings{Allen05,
author = {Martin Allen},
title = {Complexity Results for Logics of Local Reasoning and
Inconsistent Belief},
booktitle = {Proceedings of the Tenth Conference on
Theoretical Aspects of Rationality and Knowledge ({TARK-X})},
pages = {92--108},
year = 2005,
address = {Singapore}
}