Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-023 | 11th May 2000 00:00

Pseudorandom Generators in Propositional Proof Complexity

RSS-Feed

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