We call a pseudorandom generator G/sub n/:{0,1}/sup n//spl rarr/{0,1}/sup m/ hard for a propositional proof system P if P can not efficiently prove the (properly encoded) statement G/sub n/(x/sub 1/,...,x/sub n/)/spl ne/b for any string b/spl epsiv/{0,1}/sup m/. We consider a variety of "combinatorial" pseudorandom generators inspired by the Nisan-Wigderson generator on one hand, and by the construction of Tseitin tautologies on the other. We prove that under certain circumstances these generators are hard for such proof systems as resolution, polynomial calculus and polynomial calculus with resolution (PCR).
展开▼
机译：如果P不能有效证明（正确编码的）伪命题生成系统P，我们将伪随机生成器称为G / sub n /：{0,1} / sup n // spl rarr / {0,1} / sup m / ）语句G / sub n /（x / sub 1 /，...，x / sub n /）/ spl ne / b，适用于任何字符串b / spl epsiv / {0,1} / sup m /。我们考虑一方面受Nisan-Wigderson发生器启发，另一方面受Tseitin重言式构造启发的各种“组合”伪随机发生器。我们证明，在某些情况下，这些生成器对于诸如分辨率，多项式演算和带分辨率的多项式演算（PCR）之类的证明系统来说很难。
展开▼
