We call a pseudorandom generator Gn:01n01m {em hard} for a propositional proof system P if P can not efficiently prove the (properly encoded) statement Gn(x1xn)=b for {em any} string b01m . We consider a variety of ``combinatorial'' pseudorandom generators inspired by the Nisan-Wigderson generator on the 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不能有效证明{ em any}字符串b01m的(正确编码的)语句Gn(x1xn)= b,我们将其称为命题证明系统P的伪随机生成器Gn:01n01m { em hard}。我们一方面考虑由Nisan-Wigderson生成器启发,另一方面受Tseitin重言式构造启发的各种``组合''伪随机生成器。我们证明,在某些情况下,这些生成器对于诸如分辨率,多项式演算和带分辨率的多项式演算(PCR)的证明系统来说很难。
展开▼