Retraction of probabilistic computation and linear time
Lance Fortnow, Michael Sipser · 1997
In this paper, we give an oracle under which BPP is equal to probabilistic linear time, an unusual collapse of a complexity time hierarchy. In addition, we also give oracles where DP2 is contained in probabilistic linear time and where BPP has linear sized circuits, as well as oracles for the negation of these questions. This indicates that these questions will not be solved by techniques that relativize. Finally, we note that probabilistic linear time can not contain both NP and BPP, implying that there are languages solvable by interactive proof systems that can not be solved in probabilistic linear time.