Regular resolution lower bounds for the weak pigeonhole principle (Q558246)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Regular resolution lower bounds for the weak pigeonhole principle |
scientific article; zbMATH DE number 2186328
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Regular resolution lower bounds for the weak pigeonhole principle |
scientific article; zbMATH DE number 2186328 |
Statements
Regular resolution lower bounds for the weak pigeonhole principle (English)
0 references
5 July 2005
0 references
The paper is devoted to the study of the complexity of resolution proofs of the weak pigeonhole principle WPHP. It is shown that for any \(m\), any regular resolution proof for WPHP\(^{m}_{n}\) (i.e., weak pigeonhole principle with \(m\) pigeons and \(n\) holes) is of length \(\Omega (2^{n^{\epsilon}})\), where \(\epsilon > 0\) is some global constant.
0 references
weak pigeonhole principle
0 references
complexity of resolution proofs
0 references
