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 Zák's proof of the nondeterministic time hierarchy.

Authors

• Lance Fortnow
• Rahul Santhanam
• Luca Trevisan 0001

Keywords

• advice
• hierarchy theorems
• semantic classes