Derivability in certain subsystems of the logic of proofs is _2p-complete

DOI10.1016/J.APAL.2006.03.001MaRDI QIDQ866565zbMATH OpenOpenAlexFDO

Authors 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 belieflogic of proofs

Mathematics Subject Classification ID

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

Recommendations

• Kolmogorov and Gödel's approach to intuitionistic logic: current developments
• On the complexity of the reflected logic of proofs
• scientific article; zbMATH DE number 1670490
• Making knowledge explicit: how hard it is
• Logic of proofs and provability

Cites work

• Computer Science Logic
• Explicit provability and constructive semantics
• scientific article; zbMATH DE number 1670490 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1215500 (Why is no real title available?)
• scientific article; zbMATH DE number 515725 (Why is no real title available?)
• scientific article; zbMATH DE number 1114348 (Why is no real title available?)
• scientific article; zbMATH DE number 755666 (Why is no real title available?)
• scientific article; zbMATH DE number 949290 (Why is no real title available?)
• scientific article; zbMATH DE number 2209442 (Why is no real title available?)
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The logic of proofs, semantically

Cited in

(14)

• A complexity question in justification logic
• scientific article; zbMATH DE number 1670490 (Why is no real title available?)
• The Logic of Justification
• NEXP-completeness and universal hardness results for justification logic
• The logic of uncertain justifications
• The logic of justification
• Tracking evidence
• The NP-Completeness of Reflected Fragments of Justification Logics
• The logic of uncertain justifications
• Lower complexity bounds in justification logic
• The ontology of justifications in the logical setting
• Kolmogorov and Gödel's approach to intuitionistic logic: current developments
• Minimal models and the complexity of fragments of the logic of proofs
• Symmetric Logic of Proofs

This page was built for publication: Derivability in certain subsystems of the logic of proofs is \(\Pi_2^p\)-complete

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