On the polynomial-space completeness of intuitionistic propositional logic

DOI10.1007/s00153-003-0179-xzbMath1025.03030OpenAlexW2074283846MaRDI QIDQ1411664

Vítězslav Švejdar

Publication date: 29 October 2003

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

Full work available at URL: https://doi.org/10.1007/s00153-003-0179-x

zbMATH Keywords

Kripke modelsintuitionistic logicdecision problemnonclassical logicspolynomial spacelogical connectives

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (6)

Proof compression and NP versus PSPACE ⋮ The decision problem of provability logic with only one atom ⋮ An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic ⋮ Proof Compression and NP Versus PSPACE II ⋮ Disjunction property and complexity of substructural logics ⋮ Computational complexity for bounded distributive lattices with negation

Cites Work

• Intuitionistic propositional logic is polynomial-space complete
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Proof theory
• Unnamed Item
• Unnamed Item

This page was built for publication: On the polynomial-space completeness of intuitionistic propositional logic