Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR00-033 | 12th September 2001 00:00

Tautologies from pseudo-random generators

RSS-Feed




Revision #1
Authors: Jan Krajicek
Accepted on: 12th September 2001 00:00
Downloads: 1191
Keywords: 


Abstract:


Paper:

TR00-033 | 22nd May 2000 00:00

Tautologies from pseudo-random generators





TR00-033
Authors: Jan Krajicek
Publication: 6th June 2000 18:11
Downloads: 1092
Keywords: 


Abstract:

We consider tautologies formed from a pseudo-random
number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}
and in Alekhnovich et.al. \cite{ABRW}.
We explain a strategy of proving their hardness for EF via
a conjecture about bounded arithmetic formulated
in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a
purely finitary statement, in a form of a hardness condition
posed on a function, equivalent to the conjecture.
This is accompanied by a brief explanation, aimed at
non-logicians, of the relation between propositional
proof complexity and bounded arithmetic.



ISSN 1433-8092 | Imprint