Resolution lower bounds for the weak pigeonhole principle.
We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω(2nε), (for some global constant ε > 0). One corollary is that a certain propositional formulation of the statement NP ⊄ P/poly does not have short Resolut...
| में प्रकाशित: | Journal of the ACM 51, 2 (2004). |
|---|---|
| मुख्य लेखक: | |
| स्वरूप: | लेख |
| भाषा: | English |
| विषय: |