Loading...
Please wait, while we are loading the content...
Similar Documents
Lower Bounds for the Weak Pigeonhole Principle
| Content Provider | Semantic Scholar |
|---|---|
| Copyright Year | 2002 |
| Abstract | The Pigeon Hole Principle (PHP) is one of the most widely studied tautologies in propositional proof theory. The tautology PHPn is a DNF encoding of the following statement: There is no one to one mapping from n + 1 pigeons to n holes. The Weak Pigeon Hole Principle (WPHP) is a version of the pigeon hole principle that allows a larger number of pigeons. The tautologyWPHP n (form n+ 1) is a DNF encoding of the following statement: There is no one to one mapping fromm pigeons to n holes. For m > n+ 1, the weak pigeon hole principle is a weaker statement than the pigeon hole principle. Hence, it may have much shorter proofs in certain proof systems. The weak pigeon hole principle is one of the most fundamental combinatorial principles. In particular, it is used in most probabilistic counting arguments and hence in many combinatorial proofs. Moreover, as observed by Razborov, there are certain connections between the weak pigeon hole principle and the problem of P 6= NP . Indeed, the weak pigeon hole principle (with a relatively large number of pigeons) can be interpreted as a certain encodingof the following statement: There are no small DNF formulas for SAT. Hence, (in most proof systems, and in particular in Resolution), a short proof for certain formulations of the statement SAT 62 P=poly can be translated into a short proof for the weak pigeon hole principle. That is, a lower bound for the length of proofs for the weak pigeon hole principle usually implies a lower bound for the length of proofs for certain formulations of the statementNP 6 P=poly. Resolution is one of themostwidely studied propositional proof systems. The Resolution rule says that if C and D are two clauses and xi is a variable then any assignment that satisfies both of the clauses, C _ xi and D _ :xi, also |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.computer.org/csdl/proceedings/ccc/2002/1468/00/14680003.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
