Proof compression and NP versus PSPACE

DOI10.1007/S11225-017-9773-5zbMATH Open1477.03247OpenAlexW2776676667MaRDI QIDQ2631644FDOQ2631644

Authors L. N. Gordeev, Edward Hermann Haeusler

Publication date 15 May 2019

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11225-017-9773-5

zbMATH Keywords

digraphsproof theoryminimal logicpropositional complexity

Mathematics Subject Classification ID

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

Recommendations

• Proof compression and NP versus PSPACE. II
• Propositional proof compressions and DNF logic
• Proof compressions with circuit-structured substitutions
• How many times do we need an assumption to prove a tautology in minimal logic? Examples on the compression power of classical reasoning
• Exponentially huge natural deduction proofs are redundant: preliminary results on \(M_{\supset}\)

Cites work

• scientific article; zbMATH DE number 3275554 (Why is no real title available?)
• An O(n log n)-Space Decision Procedure for Intuitionistic Propositional Logic
• Intuitionistic propositional logic is polynomial-space complete
• On the polynomial-space completeness of intuitionistic propositional logic
• Proof compressions with circuit-structured substitutions
• Proof-graphs for minimal implicational logic
• Propositional proof compressions and DNF logic
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(6)

• Exponentially huge natural deduction proofs are redundant: preliminary results on \(M_{\supset}\)
• scientific article; zbMATH DE number 7564405 (Why is no real title available?)
• Proof compression and NP versus PSPACE. II
• Proof compressions with circuit-structured substitutions
• Propositional proof compressions and DNF logic
• Proof Compression and NP Versus PSPACE II: Addendum

This page was built for publication: Proof compression and NP versus PSPACE

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