Hierarchy Theorems for Probabilistic Polynomial Time

Abstract

We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 /spl les/ /spl alpha/ /spl les/ /spl beta/, BPTIME(n/sup /spl alpha//)/l /spl sube/ BPTIME(n/sup /spl beta//)/l. This result builds on and improves an earlier hierarchy of Barak using O(log log n) bits of advice. We also show that for any constant d > 0, there is a language L computable on average in BPP but not on average in BPTIME (n/sup d/). We build on Barak's techniques by using a different translation argument and by a careful application of the fact that there is a PSPACE-complete problem L such that worst-case probabilistic algorithms for L take only slightly more time than average-case algorithms.