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 proofslogic of belief

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)

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

• 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?)
• Computer Science Logic
• Explicit provability and constructive semantics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The logic of proofs, semantically

Cited in

(14)

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

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)