Quasipolynomial size proofs of the propositional pigeonhole principle

DOI10.1016/J.TCS.2015.02.005MaRDI QIDQ2344736zbMATH OpenOpenAlexWikidataFDO

Authors Samuel R. Buss

Publication date 18 May 2015

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

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

zbMATH Keywords

extended Frege proofsFrege proofspigeonhole principleproof complexitypropositional proofs

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20)

Recommendations

• Polynomial size proofs of the propositional pigeonhole principle
• Propositional proofs in Frege and extended Frege systems (abstract)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• A parity-based Frege proof for the symmetric pigeonhole principle

Cites work

• A new proof of the weak pigeonhole principle
• scientific article; zbMATH DE number 1342249 (Why is no real title available?)
• scientific article; zbMATH DE number 1860652 (Why is no real title available?)
• scientific article; zbMATH DE number 806744 (Why is no real title available?)
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• On the complexity of the parity argument and other inefficient proofs of existence
• Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets
• Polynomial size proofs of the propositional pigeonhole principle
• Proof Complexity and the Kneser-Lovász Theorem
• Propositional proofs and reductions between NP search problems
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets
• Short Proofs for the Determinant Identities
• The Complexity of Propositional Proofs
• The provably total NP search problems of weak second order bounded arithmetic
• The relative efficiency of propositional proof systems

Cited in

(15)

• A parity-based Frege proof for the symmetric pigeonhole principle
• Count\((q)\) versus the pigeon-hole principle
• Short proofs of the Kneser-Lovász coloring principle
• Towards a unified complexity theory of total functions
• Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
• scientific article; zbMATH DE number 440478 (Why is no real title available?)
• Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets
• Propositional proofs in Frege and extended Frege systems (abstract)
• Short proofs of the Kneser-Lovász coloring principle
• Polynomial size proofs of the propositional pigeonhole principle
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• An induction principle and pigeonhole principles for K-finite sets
• Towards a Unified Complexity Theory of Total Functions
• Kernelization, proof complexity and social choice
• Short proofs of the pigeonhole formulas based on the connection method

This page was built for publication: Quasipolynomial size proofs of the propositional pigeonhole principle

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