期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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).
