Probabilistic computation and linear time
Lance Fortnow, M. Sipser · 1989
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 \\Delta P 2 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. We also 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. 1 Introduction According to general belief, a problem has an efficient deterministic algorithm when the algorithm runs in time polynomial in the size of the problem. At first this seems natural, though algorithms that take time n 10 , where n is the size of the problem, strain the notion of efficiency. Most of the natural problems that have polynomial time algorithms have al...