The Complexity of Limited Belief Reasoning—The Quantifier-Free Case
The Complexity of Limited Belief Reasoning—The Quantifier-Free Case
Yijia Chen, Abdallah Saffidine, Christoph Schwering
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1774-1780.
https://doi.org/10.24963/ijcai.2018/245
The classical view of epistemic logic is that an agent knows all the logical consequences of their knowledge base. This assumption of logical omniscience is often unrealistic and makes reasoning computationally intractable. One approach to avoid logical omniscience is to limit reasoning to a certain belief level, which intuitively measures the reasoning "depth".This paper investigates the computational complexity of reasoning with belief levels. First we show that while reasoning remains tractable if the level is constant, the complexity jumps to PSPACE-complete -- that is, beyond classical reasoning -- when the belief level is part of the input. Then we further refine the picture using parameterized complexity theory to investigate how the belief level and the number of non-logical symbols affect the complexity.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Knowledge Representation and Reasoning: Reasoning about Knowlege and Belief
Knowledge Representation and Reasoning: Non-classical Logics for Knowledge Representation