Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR00-023 | 11th May 2000 00:00

#### Pseudorandom Generators in Propositional Proof Complexity

TR00-023
Authors: Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson
Publication: 11th May 2000 16:39
Keywords:

Abstract:

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).

ISSN 1433-8092 | Imprint