ECCC-Report TR00-023https://eccc.weizmann.ac.il/report/2000/023Comments and Revisions published for TR00-023en-usThu, 11 May 2000 16:39:48 +0300
Paper TR00-023
| Pseudorandom Generators in Propositional Proof Complexity |
Michael Alekhnovich,
Eli Ben-Sasson,
Alexander Razborov,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2000/023We 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).
Thu, 11 May 2000 16:39:48 +0300https://eccc.weizmann.ac.il/report/2000/023