We introduce a new framework for proving the time hierarchy theorems for heuristic classes. The main ingredient of our proof is a hierarchy theorem for sampling distributions recently proved by Watson [11]. Class Heur_∈FBPP consists of functions with distributions on their inputs that can be computed in randomized polynomial time with bounded error on all except e fraction of inputs. We prove that for every a, δ and integer k there exists a function F : {0,1}~* → {0, 1,..., k - 1} such that (F, U) ∈ Heur_∈FBPP for all ∈ > 0 and for every ensemble of distributions D_n samplable in n~a steps, (F,D) {is not an element of} Heur_(1-1/k-δ)FBPTime[n~a]. This extends a previously known result for languages with uniform distributions proved by Pervyshev [9] by handling the case k > 2. We also prove that P {is contained in} Heur_(1/2-∈)BPTime[n~k] if one-way functions exist. We also show that our technique may be extended for time hierarchies in some other heuristic classes.
展开▼
