Abstract:
We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all the common promise time classes including RTIME, NTIME \cap coNTIME, UTIME, MATIME, AMTIME and BQTIME. We show a stronger hierarchy for RTIME: For every constant c, RP/1 is not contained in RTIME(n^c)/(log n)^(1/2c). To prove this result we first prove a similar statement for NP by building on Zak's proof of the nondeterministic time hierarchy.