Probabilistic computation and linear time

ABSTRACT

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 &Dgr;P2 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.

REFERENCES

• C: Cook, S., "A hierarchy for Nondeterministic Time Complexity", JCSS7 4, 1973, pp.343-353.
• GMR: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• HaS: Hartmanis, J. and R. Stearns, "On the Computational Complexity of Algorithms", Trans. AM$117, 1965, pp. 285-306.
• HeS: F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
• K: Kannan, R., "Circuit-Size Lower Bounds and Non-reducibility to Sparse Sets", information and Control 55 1-3, 1982, pp. 40-56.
• KV: Marek Karpinski , Rutger Verbeek, Randomness, provability, and the separation of Monte Carlo time and space, Computation theory and logic, Springer-Verlag, London, 1987
• SFM: Joel I. Seiferas , Michael J. Fischer , Albert R. Meyer, Separating Nondeterministic Time Complexity Classes, Journal of the ACM (JACM), v.25 n.1, p.146-167, Jan. 1978 [doi>10.1145/322047.322061]
• S: Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
• SS: Solovay, S. and V. Strassen, "A Fast Monte- Carlo Test for Primality", SIAM j. Comp. 6, 1977, pp.84-85.
• W: Wilson, C., "Relativized Circuit Complexity", 24th FOC$, 1983, pp. 329-334.
• Z: S Zachos, Probabilistic quantifiers, adversaries, and complexity classes: an overview, Proc. of the conference on Structure in complexity theory, p.383-400, June 1986, Berkeley, California, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

General Terms:
Algorithms, Theory