Contextual Reasoning Is NP-Complete

The logic of context with the ist (c, p) modality has been proposed by McCarthy as a foundation for contextual reasoning. This paper shows that propositional logic of context is NP-complete and therefore more tractable than multimodal logics or Multi Language hierarchical logics which are PSPACE-complete, This result is given in a proof-theoretical way by providing a tableau calculus, which can be used as a decision procedure for automated reasoning. The computational gap between logic of context and modal logics is analyzed and some indications for the use of either formalisms are drawn on the basis of the tradeoff between compactness of representation and tractability of reasoning.

Authors

• Fabio Massacci

Keywords

No keywords are indexed for this paper.