Resolution lower bounds for the weak functional pigeonhole principle. (Q1401365): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q583186 |
||
Property / reviewed by | |||
Property / reviewed by: N. K. Zamov / rank | |||
Revision as of 08:35, 16 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Resolution lower bounds for the weak functional pigeonhole principle. |
scientific article |
Statements
Resolution lower bounds for the weak functional pigeonhole principle. (English)
0 references
17 August 2003
0 references
The main result of the paper is that every resolution refutation of the functional version of the pigeonhole principle must have the size \(\exp (\Omega(n/(\log m)^2))\), where \(n\) is the number of the pigeons and \(m\) is the number of holes. This fact implies an \(\exp(\Omega(n^{1/3}))\) lower bound when the number of pigeons \(m\) is arbitrary. The paper contains an overview of some open problems.
0 references
resolution method
0 references
complexity of proofs
0 references