Lower complexity bounds in justification logic

DOI10.1016/J.APAL.2011.09.010zbMATH Open1243.03026OpenAlexW2138829493MaRDI QIDQ408543FDOQ408543

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Explicit provability and constructive semantics
• The logic of proofs, semantically
• Title not available (Why is that?)
• The polynomial-time hierarchy
• The logic of justification
• Title not available (Why is that?)
• Justification logics and hybrid logics
• Introducing Justification into Epistemic Logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Justified common knowledge
• On the complexity of the reflected logic of proofs
• Title not available (Why is that?)
• Justifications for common knowledge
• Logical Omniscience Via Proof Complexity
• Why do we need justification logic?
• Derivability in certain subsystems of the logic of proofs is \(\Pi_2^p\)-complete
• Self-referential justifications in epistemic logic
• A complexity question in justification logic
• Existential semantics for modal logic
• The deduction rule and linear and near-linear proof simulations
• 2004 Annual Meeting of the Association for Symbolic Logic
• The NP-Completeness of Reflected Fragments of Justification Logics
• Title not available (Why is that?)

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)