Relativized questions involving probabilistic algorithms

ABSTRACT

Let R @@@@ NP be the collection of languages L such that for some polynomial time computable predicate P(x,y) and constant k, L &equil; {x|@@@@y, |y|&equil;|x|k,P(x,y)} &equil; {x|@@@@ at least 2|x|k−1 values of y, |y|&equil;|x|k,P(x,y)}. Let U @@@@ NP be the collection of languages L such that for some polynomial time computable predicate P(x,y) and constant k, L &equil; {x|@@@@y,|y|&equil;|x|k,P(x,y)}&equil; {x|@@@@ unique y, |y|&equil;|x|k,p(x,y)}. Let RA,UA, PA,NPA,CO-NPA be the relativization of these classes with respect to an oracle A as in [ 5 ]. Then for some oracle E (NPE @@@@ CO-NPE) &equil; UE &equil; RE &equil; PE @@@@ NPE while for some other oracle D CO-NPD &equil; NPD &equil; UD &equil; RD @@@@ PD.

REFERENCES

• 1: Leonard Adleman , Kenneth Manders, Reducibility, randomness, and intractibility (Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.151-163, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803405]
• 2: T. Baker, J. Gill, and R. Solovay, "Relativizations of the P&equil;NP? Question", SIAM J. on Computing, 1977, 431-442.
• 3: T. Baker and A. Selman, "A Second Step Toward the Polynomial Hierarchy", 17th Ann. Symposium on Foundations of Computer Science, 1976, 71-75.
• 4: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 5: John T. Gill, III, Computational complexity of probabilistic Turing machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.91-95, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803889]
• 6: Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
• 7: R. Ladner and N. Lynch, "Relativization of Questions about Log Space Computability", Math Syst. Theory 10, 1976, 19-32.
• 8: A. Meyer and L. Stockmeyer, "The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space", 13th Ann. IEEE Symp. on Switching and Automata Theory, 1972, 125-129.
• 9: Gary L. Miller, Riemann's Hypothesis and tests for primality, Proceedings of seventh annual ACM symposium on Theory of computing, p.234-239, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803773]
• 10: R. Solovay and V. Strassen, "A Fast MonteCarlo Test for Primality", SIAM J. on Computing 6, 1, 1977, 84-85.
• 11: L. Valiant, "Relative Complexity of Checking and Evaluating", Information Processing 5, 1, 1976, 20-23.