Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
From MaRDI portal
Publication:5427258
DOI10.1093/logcom/exm029zbMath1126.03024arXivcs/0603019OpenAlexW2287532945MaRDI QIDQ5427258
Leandros Chaves Rêgo, Joseph Y. Halpern
Publication date: 19 November 2007
Published in: Journal of Logic and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0603019
Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Knowledge representation (68T30) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
An NP-complete fragment of fibring logic ⋮ Unnamed Item ⋮ The complexity of identifying characteristic formulae ⋮ Parameterized modal satisfiability ⋮ Epistemic closure and epistemic logic. I: Relevant alternatives and subjunctivism ⋮ Reasoning about knowledge of unawareness
