We study the existence of time hierarchies for heuristic algorithms. We prove that a time hierarchy exists for heuristic algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Further, we present an alternative approach to proving time hierarchies for heuristic algorithms in BPP. This leads to a simpler proof than the one known before.

We show that for any reasonable semantic model of computation and for any positive integer a and rationals 1 ≤ c < d, there exists a language computable in time n d with a bits of advice but not in time n c with a bits of advice. Our result implies the first such hierarchy theorem for randomized machines with zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur.Merlin games of any signature, etc. Our argument yields considerably simpler proofs of known hierarchy theorems with one bit of advice for randomized and quantum machines with two-sided error. Our paradigm also allows us to derive stronger separation results in which the machine with the smaller running time can receive more advice than the one with the larger running time. We present a unified way to derive such results for randomized and quantum machines with two-sided error and for randomized machines with one-sided error.

We show that for any reasonable semantic model of computation and for any positive integer a and rationals 1dwith a bits of advice but not in time ncwith a bits of advice. A semantic model is one for which there exists a computable enumeration that contains all machines in the model but may also contain others. We call such a model reasonable if it has an efficient universal machine that can be complemented within the model in exponential time and if it is efficiently closed under deterministic transducers. Our result implies the first such hierarchy theorem for randomized machines with zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur-Merlin games of any signature, etc. Our argument yields considerably simpler proofs of known hierarchy theorems with one bit of advice for randomized and quantum machines with two-sided error. Our paradigm also allows us to derive stronger separation results in a unified way. For models that have an efficient universal machine that can be simulated deterministically in exponential time and that are efficiently closed under randomized reductions with two-sided error, we establish the following: For any constants a and c, there exists a language computable in polynomial time with one bit of advice but not in time ncwith a log n bits of advice. The result applies to randomized and quantum machines with two-sided error. For randomized machines with one-sided error, our approach yields that for any constants a and c there exists a language computable in polynomial time with one bit of advice but not in time ncwith a (log n)1c/ bits of advice