Easiness Assumptions and Hardness Tests: Trading Time for Zero Error

摘要

We propose a new approach toward derandomization in the uniform setting, where it is computationally hard to find possible mistakes in the simulation of a given probabilistic algorithm. The approach consists in combining both easiness and hardness complexity assumptions: if a derandomization method based on an easiness assumption fails, then we obtain a certain hardness test that can be used to remove error in BPP algorithms. As an application, we prove that every RP algorithm can be simulated by a zero-error probabilistic algorithm, running in expected subexponential time, that appears correct infinitely often (i.o.) to every efficient adversary. A similar result by Impagliazzo and Wigderson (FOCS'98) states that BPP allows deterministic subexponential-time simulations that appear correct with respect to any efficiently sampleable distribution i.o., under the assumption that EXP≠BPP; in contrast, our result does not rely on any unproven assumptions. As another application of our techniques, we get the following gap theorem for ZPP: either every RP algorithm can be simulated by a deterministic subexponential-time algorithm that appears correct i.o. to every efficient adversary or EXP=ZPP. In particular, this implies that if ZPP is somewhat easy, e.g., ZPP⊆DTIME(2nc) for some fixed constant c, then RP is subexponentially easy in the uniform setting described above.