Contextual Reasoning Is NP-Complete

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Knowledge Bases & Context

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.