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).
المؤلف الرئيسي:	Raz, R.
التنسيق:	مقال
اللغة:	الإنجليزية
الموضوعات:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Complexity of proof procedures. Mathematical logic and formal languages. Mathematical logic. Proof theory. Theory.