Regular resolution lower bounds for the weak pigeonhole principle (Q558246): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Property / review text | |||
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. | |||
| Property / review text: 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. / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Roman Murawski / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 03F20 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 68Q17 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 2186328 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
weak pigeonhole principle | |||
| Property / zbMATH Keywords: weak pigeonhole principle / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
complexity of resolution proofs | |||
| Property / zbMATH Keywords: complexity of resolution proofs / rank | |||
Normal rank | |||
| 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 | |||
| links / mardi / name | links / mardi / name | ||
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
