Lower complexity bounds in justification logic

DOI10.1016/J.APAL.2011.09.010MaRDI QIDQ408543zbMATH OpenOpenAlexFDO

Authors 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 complexityjustification logiclogic of proofs\(\Pi^p_2\)-completenessderivability problem

Mathematics Subject Classification ID

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

Recommendations

• The NP-Completeness of Reflected Fragments of Justification Logics
• A complexity question in justification logic
• A complexity question in justification logic
• On the Complexity of Two-Agent Justification Logic
• NEXP-completeness and universal hardness results for justification logic

Cites work

• scientific article; zbMATH DE number 1670490 (Why is no real title available?)
• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1114348 (Why is no real title available?)
• scientific article; zbMATH DE number 2110413 (Why is no real title available?)
• 2004 Annual Meeting of the Association for Symbolic Logic
• A complexity question in justification logic
• Derivability in certain subsystems of the logic of proofs is _2p-complete
• Existential semantics for modal logic
• Explicit provability and constructive semantics
• Introducing Justification into Epistemic Logic
• Justification logics and hybrid logics
• Justifications for common knowledge
• Justified common knowledge
• Logical Omniscience Via Proof Complexity
• On the complexity of the reflected logic of proofs
• Self-referential justifications in epistemic logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The NP-Completeness of Reflected Fragments of Justification Logics
• The deduction rule and linear and near-linear proof simulations
• The logic of justification
• The logic of proofs, semantically
• The polynomial-time hierarchy
• Why do we need justification logic?

Cited in

(7)

• Decidability for some justification logics with negative introspection
• A complexity question in justification logic
• On the Complexity of Two-Agent Justification Logic
• NEXP-completeness and universal hardness results for justification logic
• A complexity question in justification logic
• The NP-Completeness of Reflected Fragments of Justification Logics
• Efficient Approximation of Well-Founded Justification and Well-Founded Domination

This page was built for publication: Lower complexity bounds in justification logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408543)