Lower complexity bounds in justification logic

DOI10.1016/j.apal.2011.09.010zbMath1243.03026OpenAlexW2138829493MaRDI QIDQ408543

Samuel R. Buss, Roman Kuznets

Publication date: 10 April 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.09.010

zbMATH Keywords

computational complexitylogic of proofsjustification logic\(\Pi^p_2\)-completenessderivability problem

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

NEXP-Completeness and Universal Hardness Results for Justification Logic ⋮ A complexity question in justification logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Justification logics and hybrid logics
• The logic of proofs, semantically
• Derivability in certain subsystems of the logic of proofs is \(\Pi_2^p\)-complete
• Self-referential justifications in epistemic logic
• The polynomial-time hierarchy
• Justified common knowledge
• On the complexity of the reflected logic of proofs
• Explicit Provability and Constructive Semantics
• Justifications for common knowledge
• A Complexity Question in Justification Logic
• The deduction rule and linear and near-linear proof simulations
• 2004 Annual Meeting of the Association for Symbolic Logic
• Introducing Justification into Epistemic Logic
• THE LOGIC OF JUSTIFICATION
• The NP-Completeness of Reflected Fragments of Justification Logics
• 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: Lower complexity bounds in justification logic