ECCC-Report TR04-098https://eccc.weizmann.ac.il/report/2004/098Comments and Revisions published for TR04-098en-usFri, 12 Nov 2004 16:28:13 +0200
Paper TR04-098
| Promise Hierarchies |
Lance Fortnow,
Rahul Santhanam,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2004/098We 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.
Fri, 12 Nov 2004 16:28:13 +0200https://eccc.weizmann.ac.il/report/2004/098