ECCC-Report TR00-033https://eccc.weizmann.ac.il/report/2000/033Comments and Revisions published for TR00-033en-usWed, 12 Sep 2001 00:00:00 +0300
Revision 1
| Tautologies from pseudo-random generators |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2000/033#revision1Wed, 12 Sep 2001 00:00:00 +0300https://eccc.weizmann.ac.il/report/2000/033#revision1
Paper TR00-033
| Tautologies from pseudo-random generators |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2000/033We 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.
Tue, 06 Jun 2000 18:11:54 +0300https://eccc.weizmann.ac.il/report/2000/033