Proof Compression and NP Versus PSPACE II

DOI10.18778/0138-0680.2020.16zbMath1477.03246OpenAlexW3048669164MaRDI QIDQ5147748

Edward Hermann Haeusler, L. N. Gordeev

Publication date: 28 January 2021

Published in: Bulletin of the Section of Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.18778/0138-0680.2020.16

zbMATH Keywords

computational complexitysequent calculusnatural deductionminimal logic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (1)

Proof Compression and NP Versus PSPACE II: Addendum

Cites Work

• Intuitionistic propositional logic is polynomial-space complete
• On the polynomial-space completeness of intuitionistic propositional logic
• Proof compression and NP versus PSPACE
• Embedding classical in minimal implicational logic
• An O(n log n)-Space Decision Procedure for Intuitionistic Propositional Logic
• Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Proof Compression and NP Versus PSPACE II