Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-098 | 5th November 2004 00:00

Promise Hierarchies

RSS-Feed




TR04-098
Authors: Lance Fortnow, Rahul Santhanam, Luca Trevisan
Publication: 12th November 2004 16:28
Downloads: 3088
Keywords: 


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.



ISSN 1433-8092 | Imprint