[FOM] Questions on Complexity Theory

[Rahul Santhanam]

>
> ZPP < ExpTime can only be proved by current techniques by showing how to
> solve ZPP problems in sub-exponential time.  Candidate polynomial time
> derandomization algorithms for BPP (and hence ZPP) are known.  They use
> pseudo-random number generators to produce pseudo-random data from
> logarithmically sized seeds, and iterate over all seeds.   However,
> existence of secure pseudo-random number generators implies P<NP, and
> hence is unlikely to be proved soon.

Nice synopsis, but the last statement is inaccurate. To solve ZPP problems
in sub-exponential time, it is only required to show that there is an
exponential-time language that is not solvable by polynomial sized
circuits with AND and OR gates. This is possibly a much simpler task than
separating P from NP.

Interestingly, there is a good candidate language for the lower bound
whose definition itself involves randomess: the set of all strings of high
time-bounded Kolmogorov complexity (as defined by Levin).

Rahul.