The NP-Completeness of Reflected Fragments of Justification Logics

DOI10.1007/978-3-540-92687-0_9zbMath1211.03035OpenAlexW1532416084MaRDI QIDQ3605524

Roman Kuznets, Samuel R. Buss

Publication date: 24 February 2009

Published in: Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92687-0_9

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logics of knowledge and belief (including belief change) (03B42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Lower complexity bounds in justification logic ⋮ Towards NP-P via proof complexity and search ⋮ A complexity question in justification logic

Cites Work

• Unnamed Item
• Derivability in certain subsystems of the logic of proofs is \(\Pi_2^p\)-complete
• Justified common knowledge
• On the complexity of the reflected logic of proofs
• Explicit Provability and Constructive Semantics
• The deduction rule and linear and near-linear proof simulations
• Self-referentiality of Justified Knowledge
• THE LOGIC OF JUSTIFICATION
• Logical Omniscience Via Proof Complexity
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Why Do We Need Justification Logic?

This page was built for publication: The NP-Completeness of Reflected Fragments of Justification Logics