Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution
Alexander Alexandrovich Razborov · Annals of Mathematics · 2014
A pseudorandom generator Gn : {0, 1} n → {0, 1} m is hard for a propositional proof system P if (roughly speaking) P cannot efficiently prove the statement Gn(x1, . . ., xn) = b for any string b ∈ {0, 1} m .We present a function (m ≥ 2 n Ω(1)) generator which is hard for Res(ε 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(ε log t) proof of the principle ¬Circuitt(fn) (asserting that the circuit size of a Boolean function fn in n variables is greater than t) must have size exp(t Ω(1) ).In particular, Res(log log N ) (N ∼ 2 n is the overall number of propositional variables) does not possess efficient proofs of NP ⊆ 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 PHP 2n n is hard for Res(ε log n/ log log n).