Contextual reasoning is NP-complete
Fabio Massacci · 1996
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. Introduction In the last few years there has been a renewed interest in the use of contexts for natural language understanding and knowledge representation form. Indeed, the discussion about contextual reasoning in AI can be traced back to McCarthy's Turing Award Lecture in 1971, and has been recently tac...