Approximation and Small-Depth Frege Proofs
From MaRDI portal
Publication:4027856
DOI10.1137/0221068zbMath0762.03020OpenAlexW2135672707MaRDI QIDQ4027856
Alasdair Urquhart, Toniann Pitassi, Stephen J. Bellantoni
Publication date: 9 March 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e6d642d005067afdee2f7740b2536d87de269d6e
lower boundproof theorypropositional pigeonhole principleapproximate proofcomplexity of propositional proof systems
Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Classical propositional logic (03B05) Complexity of proofs (03F20)
Related Items
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies, Formulas versus Circuits for Small Distance Connectivity, Simplified lower bounds for propositional proofs, Typical forcings, NP search problems and an extension of a theorem of Riis, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Exponential lower bounds for the pigeonhole principle, Partially definable forcing and bounded arithmetic, Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs, Bounded-depth Frege complexity of Tseitin formulas for all graphs, Unnamed Item, A Logical Autobiography, Reflections on Proof Complexity and Counting Principles, Hardness and optimality in QBF proof systems modulo NP
