Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies

DOI10.1016/J.TCS.2006.03.011MaRDI QIDQ2500481zbMATH OpenOpenAlexFDO

Authors Samuel R. Buss

Publication date 16 August 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.03.011

zbMATH Keywords

resolutionproof complexitygraph connectivitypropositional logicHex game

Mathematics Subject Classification ID

Connectivity (05C40) Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 1114019
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Polynomial size proofs of the propositional pigeonhole principle
• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• On Small-depth Frege Proofs for Tseitin for Grids

Cites work

• scientific article; zbMATH DE number 3563392 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• An exponential separation between the parity principle and the pigeonhole principle
• Cutting planes, connectivity, and threshold logic
• Exponential lower bounds for the pigeonhole principle
• Hex strategy: making the right connections
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Lower bounds to the size of constant-depth propositional proofs
• On Interpolation and Automatization for Frege Systems
• On the complexity of the parity argument and other inefficient proofs of existence
• Polynomial size proofs of the propositional pigeonhole principle
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• The Game of Hex and the Brouwer Fixed-Point Theorem
• The independence of the modulo \(p\) counting principles
• The relative complexity of NP search problems
• The relative efficiency of propositional proof systems

Cited in

(4)

• Planar and grid graph reachability problems
• 2-D Tucker is PPA complete
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• On Small-depth Frege Proofs for Tseitin for Grids

This page was built for publication: Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies

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