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

DOI10.1007/S00153-014-0397-4zbMATH Open1339.03057arXiv1305.6065OpenAlexW2089432821MaRDI QIDQ482919FDOQ482919

Authors: Fedor N. Pakhomov 

Publication date: 15 December 2014

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

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.

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

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

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)

Cites Work

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

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)