Derivability in certain subsystems of the logic of proofs is \(\Pi_2^p\)-complete

DOI10.1016/j.apal.2006.03.001zbMath1112.03054OpenAlexW2138312950MaRDI QIDQ866565

Robert Saxon Milnikel

Publication date: 14 February 2007

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.2006.03.001

zbMATH Keywords

complexitylogic of proofslogic of belief

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Provability logics and related algebras (e.g., diagonalizable algebras) (03F45)

Related Items

The Logic of Uncertain Justifications ⋮ NEXP-Completeness and Universal Hardness Results for Justification Logic ⋮ The logic of uncertain justifications ⋮ Lower complexity bounds in justification logic ⋮ The Logic of Justification ⋮ The ontology of justifications in the logical setting ⋮ A complexity question in justification logic ⋮ THE LOGIC OF JUSTIFICATION ⋮ Tracking Evidence ⋮ The NP-Completeness of Reflected Fragments of Justification Logics ⋮ Symmetric Logic of Proofs

Cites Work

• The logic of proofs, semantically
• Explicit Provability and Constructive Semantics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Computer Science Logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item