Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-054 | 19th May 2005 00:00

Time Hierarchies for Computations with a Bit of Advice

RSS-Feed

Abstract:

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, MATime, AMTime and BQTime. It also significantly simplifies the previously known proofs of hierarchies for BPTime and RPTime with advice.



ISSN 1433-8092 | Imprint