hierarchies for semantic classes
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 common semantic time classes including RTIME, NTIME ? 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 Zk's proof of the nondeterministic time hierarchy.
semantic classes hierarchy theorems advice