[FOM] Questions on Complexity Theory
rahul at cs.uchicago.edu
Thu Dec 15 01:48:31 EST 2005
> 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).
More information about the FOM