On the weak pigeonhole principle
From MaRDI portal
Publication:2773242
DOI10.4064/fm170-1-8zbMath0987.03051OpenAlexW2026967932WikidataQ106785109 ScholiaQ106785109MaRDI QIDQ2773242
Publication date: 21 February 2002
Published in: Fundamenta Mathematicae (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4064/fm170-1-8
lower boundsresolutionbounded arithmeticRamsey theoremproof complexityone-way functionsweak pigeonhole principle
First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (45)
From Small Space to Small Width in Resolution ⋮ On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies ⋮ On the automatizability of resolution and related propositional proof systems ⋮ On the complexity of resolution with bounded conjunctions ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ Nisan-Wigderson generators in proof systems with forms of interpolation ⋮ Approximate counting and NP search problems ⋮ Substitutions into propositional tautologies ⋮ A note about \(k\)-DNF resolution ⋮ Hardness assumptions in the foundations of theoretical computer science ⋮ Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Parity Games and Propositional Proofs ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ Towards NP-P via proof complexity and search ⋮ A note on propositional proof complexity of some Ramsey-type statements ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Lower bounds for \(k\)-DNF resolution on random 3-CNFs ⋮ A lower bound on the size of resolution proofs of the Ramsey theorem ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams ⋮ Unnamed Item ⋮ On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ Resolution over linear equations and multilinear proofs ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ The treewidth of proofs ⋮ 2003 Annual Meeting of the Association for Symbolic Logic ⋮ The Complexity of Propositional Proofs ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION ⋮ Random resolution refutations ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Separation results for the size of constant-depth propositional proofs ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution ⋮ Spines of random constraint satisfaction problems: definition and connection with computational complexity
This page was built for publication: On the weak pigeonhole principle
