Abstract
A series of recent results has characterized membership in certain complexity classes in terms of specific types of reductions: a set is in the class if and only if it is reducible to almost every set. We define a new notion of reducibility which characterizes the classes ∑ p k ,k>0, of the polynomial-time hierarchy in this way. As an application, we show that the levels of the polynomial-time hierarchy are distinct if and only if uniform witnesses to this separation exist.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Ambos-Spies, Randomness, relativizations, and polynomial reducibilities,Proc. 1st Conf. on Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, Berlin, 1986, pp. 23–34.
L. Babai and S. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes,J. Comput. System Sci. 36 (1988), 254–276.
J. Balcázar, J. Díaz, and J. Gabarró,Structural Complexity, I, Springer-Verlag, Berlin, 1988.
D. Bennett and J. Gill, Relative to a random oracleA, P A≠NP A ≠co-NP A with probability 1,SIAM J. Comput. 10 (1981), 96–113.
R. Book, T. Long, and A. Selman, Qualitative relativizations of complexity classes,J. Comput. System Sci. 30 (1985), 395–413.
W. Feller,An Introduction to Probability Theory and Its Applications, I, Wiley, New York, 1957.
W. Feller,An Introduction to Probability Theory and Its Applications, II, Wiley, New York, 1971.
J. Gill, Computational complexity of probabilistic Turing machines,SIAM J. Comput. 7 (1977), 675–695.
R. Ladner, N. Lynch, and A. Selman, A comparison of polynomial-time reducibilities,Theoret. Comput. Sci. 1 (1975), 103–123.
T. Long, Strong nondeterministic polynomial-time reducibilities,Theoret. Comput. Sci. 21 (1982), 1–25.
N. Nisan and A. Wigderson, Hardness vs. randomness,Proc. 29th IEEE Symp. Foundations of Computer. Science (1988), pp. 2–11.
C. Rich, Positive relativizations of theP = ?NP problems,J. Comput. System Sci. 38 (1989), 511–523.
U. Schöning, Probabilistic complexity classes and lowness,Proc. 2nd IEEE Conf. on Structure in Complexity Theory (1987), pp. 2–8.
L. Stockmeyer, The polynomial-time hierarchy,Theoret. Comput. Sci. 3 (1977), 1–22.
S. Tang and R. Book, Polynomial reducibilities and almost every oracle set,Theoret. Comput. Sci., to appear.
S. Tang and O. Watanabe, On tally relativizations ofBP-complexity classes,SIAM J. Comput. 18 (1989), 449–462.
C. Wrathall, Complete sets and the polynomial time hierarchy,Theoret. Comput. Sci. 3 (1977), 23–33.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under Grant CCR86-11980.
Rights and permissions
About this article
Cite this article
Book, R.V., Tang, S. Characterizing polynomial complexity classes by reducibilities. Math. Systems Theory 23, 165–174 (1990). https://doi.org/10.1007/BF02090773
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02090773