On the complexity of the closed fragment of Japaridze's provability logic

DOI10.1007/S00153-014-0397-4MaRDI QIDQ482919zbMATH OpenOpenAlexFDO

Authors Fedor N. Pakhomov

Publication date 15 December 2014

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.6065

zbMATH Keywords

computational complexityprovability logicclosed fragment

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Provability logics and related algebras (e.g., diagonalizable algebras) (03F45)

Abstract: We consider well-known provability logic GLP. We prove that the GLP-provability problem for variable-free polymodal formulas is PSPACE-complete. For a number n, let L^n_0 denote the class of all polymodal variable-free formulas without modalities <n>, <n+1>,... . We show that, for every number n, the GLP-provability problem for formulas from L^n_0 is in PTIME.

Recommendations

• On the positive fragment of the polymodal provability logic GLP
• A Finitary Treatment of the Closed Fragment of Japaridze's Provability Logic
• On provability logics with linearly ordered modalities
• scientific article; zbMATH DE number 6302903
• A simplified proof of arithmetical completeness theorem for provability logic GLP

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 2196586 (Why is no real title available?)
• scientific article; zbMATH DE number 5046774 (Why is no real title available?)
• A Finitary Treatment of the Closed Fragment of Japaridze's Provability Logic
• On provability logics with linearly ordered modalities
• On strong provability predicates and the associated modal logics
• On the positive fragment of the polymodal provability logic GLP
• PSPACE-decidability of Japaridze's polymodal logic
• Reflection principles and provability algebras in formal arithmetic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The closed fragment of IL is PSPACE hard
• The decision problem of provability logic with only one atom
• Time bounded random access machines

Cited in

(9)

• Closed Fragments of Provability Logics of Constructive Theories
• An inside view of EXP; or, The closed fragment of the provability logic of IΔ₀ + Ω₁ with a prepositional constant for EXP
• The closed fragment of IL is PSPACE hard
• Linear \(\mathrm{GLP}\)-algebras and their elementary theories
• A Finitary Treatment of the Closed Fragment of Japaridze's Provability Logic
• On the positive fragment of the polymodal provability logic GLP
• Axiomatization and polynomial solvability of strictly positive fragments of certain modal logics
• Modal companions of \(K4^+\)
• PSPACE-decidability of Japaridze's polymodal logic

This page was built for publication: On the complexity of the closed fragment of Japaridze's provability logic

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