How many times do we need an assumption to prove a tautology in minimal logic? Examples on the compression power of classical reasoning

DOI10.1016/j.entcs.2015.06.004zbMath1352.03067WikidataQ113317782 ScholiaQ113317782MaRDI QIDQ2520659

Edward Hermann Haeusler

Publication date: 16 December 2016

Full work available at URL: https://doi.org/10.1016/j.entcs.2015.06.004

zbMATH Keywords

proof theory; natural deduction; minimal propositional logic; propositional logic complexity

Mathematics Subject Classification ID

03B35: Mechanization of proofs and logical operations

03B05: Classical propositional logic

03F20: Complexity of proofs

Related Items

A unified procedure for provability and counter-model generation in minimal implicational logic

Cites Work

• A new normalization strategy for the implicational fragment of classical propositional logic
• The intractability of resolution
• Proof theory. 2nd ed
• Intuitionistic propositional logic is polynomial-space complete
• Eigenvariables, bracketing and the decidability of positive minimal predicate logic
• On cut elimination in the presence of perice rule
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Lower bounds to the size of constant-depth propositional proofs
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item