Regular resolution lower bounds for the weak pigeonhole principle (Q558246): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
| (One intermediate revision by one other user not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/s00493-004-0029-4 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2001378190 / rank | |||
Normal rank | |||
Latest revision as of 00:19, 20 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Regular resolution lower bounds for the weak pigeonhole principle |
scientific article |
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
