Resolution proofs of generalized pigeonhole principles

DOI10.1016/0304-3975(88)90072-2zbMath0709.03006OpenAlexW2062912795MaRDI QIDQ920967

Samuel R. Buss, György Turán

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90072-2

zbMATH Keywords

resolution refutationFrege systemspolynomial equivalencegeneralized pigeonhole principlepropositional clausessize of proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)

Related Items

The complexity of the pigeonhole principle, Width versus size in resolution proofs, Davis-Putnam resolution versus unrestricted resolution, Cutting planes, connectivity, and threshold logic, Lower bounds to the size of constant-depth propositional proofs, Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms, Resolution lower bounds for the weak functional pigeonhole principle., A feasibly constructive lower bound for resolution proofs, The symmetry rule in propositional logic, An Introduction to Lower Bounds on Resolution Proof Systems, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, A new proof of the weak pigeonhole principle, Unrestricted resolution versus N-resolution, Unnamed Item, Satisfiability via Smooth Pictures, Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II, Lower bounds for the weak pigeonhole principle and random formulas beyond resolution, Group cancellation and resolution

Cites Work

• Unnamed Item
• On the complexity of cutting-plane proofs
• The intractability of resolution
• Polynomial size proofs of the propositional pigeonhole principle
• Hard examples for resolution
• The relative efficiency of propositional proof systems
• Provability of the pigeonhole principle and the existence of infinitely many primes