Time Hierarchies for Computations with a Bit of Advice
Konstantin Pervyshev · Electronic colloquium on computational complexity · 2005
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 ( ZPTime[n b ]=1. The technique introduced in this paper is very general and gives the same hierarchy for NTime\coNTime, UTime, MATime, AMTime and BQTime. It also signican tly simplies the previously known proofs of hierarchies for BPTime and RPTime with advice.