[FOM] Re: Questions on Complexity Theory

[Dmytro Taranovsky]

High on the list of almost absurd statements that we do not know how to
disprove is the claim ZPP = ExpTime.  It asserts that random data
(formally, all but an exponentially small percentage of strings) are in
fact a vast store wisdom allowing us to solve exponential time complete
problems in polynomial time.  Unsuitable strings passed as random may be
rejected but will not lead to mistakes.  Present knowledge does not rule
out linear running time (reasonably defined) when the exponent is linear
(and output has at most linear length in terms of input).

There are oracles relative to which ZPP = ExpTime.  The oracles answer
exponential-time complexity queries that are prefixed with a random
string, specifically rejecting prefixes that are too easily computable.

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.

Also, the question of whether solving exponential time complete problems
is physically feasible is wide open.

Dmytro Taranovsky