TR00-023 Authors: Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

Publication: 11th May 2000 16:39

Downloads: 1039

Keywords:

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em

hard} for a propositional proof system $P$ if $P$ can not efficiently

prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for

{\em any} string $b\in\{0,1\}^m$. 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).