Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution

• 成果类型: Article
• 署名作者: Razborov, Alexander A.
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2015.181.2.1
• 发表日期: 2015
• 页码: 415-472
• 关键词: weak pigeonhole principle; Lower bounds; proofs; complexity

摘要

A pseudorandom generator G(n) : {0, 1}(n) -> {0, 1}(m) is hard for a propositional proof system P if (roughly speaking) P cannot efficiently prove the statement G(n) (x(1),...,x(n)) not equal b for any string b is an element of {0, 1}(m). We present a function (m >= 2(n Omega(1))) generator which is hard for Res(epsilon log n); here Res(k) is the propositional proof system that extends Resolution by allowing k-DNFs instead of clauses. As a direct consequence of this result, we show that whenever t >= n(2), every Res(epsilon log t) proof of the principle -Circuit(t) (f(n)) (asserting that the circuit size of a Boolean function f(n) in n variables is greater than t) must have size exp(t(Omega(1))). In particular, Res(log log N) (N similar to 2(n) is the overall number of propositional variables) does not possess efficient proofs of NP not subset of P/poly. Similar results hold also for the system PCR (the natural common extension of Polynomial Calculus and Resolution) when the characteristic of the ground field is different from 2. As a byproduct, we also improve on the small restriction switching lemma due to Segerlind, Buss and Impagliazzo by removing a square root from the final bound. This in particular implies that the (moderately) weak pigeonhole principle PHPn2n is hard for Res(epsilon log n/log log n).