Publication:1411664

DOI10.1007/S00153-003-0179-XzbMATH Open1025.03030OpenAlexW2074283846MaRDI QIDQ1411664FDOQ1411664

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

intuitionistic logicKripke modelsnonclassical logicspolynomial spacedecision problemlogical connectives

Mathematics Subject Classification ID

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

Cites Work

• Proof theory
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Intuitionistic propositional logic is polynomial-space complete
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

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

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

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