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

DOI10.1016/J.TCS.2006.03.011zbMATH Open1094.03044OpenAlexW2086897006MaRDI QIDQ2500481FDOQ2500481

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

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

zbMATH Keywords

resolutionproof complexitygraph connectivitypropositional logicHex game

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Planar and grid graph reachability problems
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• 2-D Tucker is PPA complete
• 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)