Proof compression and NP versus PSPACE
From MaRDI portal
Publication:2631644
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
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}\)
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Title not available (Why is that?)
- Intuitionistic propositional logic is polynomial-space complete
- On the polynomial-space completeness of intuitionistic propositional logic
- Proof compressions with circuit-structured substitutions
- An O(n log n)-Space Decision Procedure for Intuitionistic Propositional Logic
- Proof-graphs for minimal implicational logic
- Propositional proof compressions and DNF logic
Cited In (7)
- Exponentially huge natural deduction proofs are redundant: preliminary results on \(M_{\supset}\)
- Proof compressions with circuit-structured substitutions
- Title not available (Why is that?)
- AND-compression of NP-complete problems: streamlined proof and minor observations
- Propositional proof compressions and DNF logic
- Proof compression and NP versus PSPACE. II
- 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)
