zbMATH — the first resource for mathematics

Strong and robustly strong polynomial-time reducibilities to sparse sets. (English) Zbl 0735.68032
Strong nondeterministic machines are those types of Turing machines that define the class \(\text{NP}\cap\text{co-NP}\). When equipped with the additional feature of an ”advice”, as studied by Karp and Lipton, two different definitions are possible: a robust and non-robust version. Both versions are studied in this paper and compared. Related to this research, an oracle-restricted positive relativization of the probabilistic class ZPP is developed.
Reviewer: U.Schöning

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Abadi, M.; Feigenbaum, J.; Kilian, J., On hiding information from an oracle, Proc. 19th ACM STOC, 195-203, (1987)
[2] Adleman, L.; Manders, K., Reducibility, randomness, and intractability, Proc. 9th ACM STOC, 151-163, (1977)
[3] Balcázar, J.L.; Book, R.V., Sets with small generalized Kolmogorov complexity, Acta inform., 23, 679-688, (1986) · Zbl 0616.68046
[4] Balcázar, J.L.; Book, R.V.; Schöning, U., The polynomial time hierarchy and sparse oracles, J. ACM, 33, 603-617, (1986) · Zbl 0625.68033
[5] Balcázar, J.L.; Díaz, J.; Gabarró, J., Structural complexity I, (1988), Springer Berlin · Zbl 0638.68040
[6] Book, R.; Long, T.; Selman, A., Quantitative relativizations of complexity classes, SIAM J. comput., 13, 461-487, (1984) · Zbl 0599.03041
[7] Book, R.; Long, T.; Selman, A., Qualitative relativizations of complexity classes, J. comput. system sci., 30, 395-413, (1985) · Zbl 0569.03016
[8] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[9] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. comput., 6, 675-695, (1977) · Zbl 0366.02024
[10] Hartmanis, J., On sparse sets in NP-P, Inform. process. lett., 16, 55-60, (1983) · Zbl 0501.68014
[11] Hemachandra, L., Counting in structural complexity theory, ()
[12] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[13] Kadin, J., Restricted Turing reducibilities and the structure of the polynomial time hierarchy, ()
[14] Kämper, J., Non-uniform proof systems: a new framework to describe non-uniform and probabilistic complexity classes, () · Zbl 0666.68047
[15] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, Proc. 12th ACM STOC, 302-309, (1980)
[16] Long, T., Strong nondeterministic polynomial time reducibilities, Theoret. comput. sci., 21, 1-25, (1982) · Zbl 0521.03028
[17] Long, T.; Selman, A., Relativizing complexity classes with sparse oracles, J. ACM, 33, 618-628, (1986)
[18] Pippenger, N., On simultaneous resource bounds, Proc. 20th IEEE FOCS, 307-311, (1979)
[19] Russo, D., Structural properties of complexity classes, ()
[20] Schöning, U., A low and high hierarchy within NP^{+}, J. comput. system sci., 27, 14-28, (1983)
[21] Schöning, U., On small generators, Theoret. comput. sci., 34, 337-341, (1984) · Zbl 0558.68040
[22] Stockmeyer, L., The polynomial time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024
[23] Yap, C., Some consequences of nonuniform conditions on uniform classes, Theoret. comput. sci., 27, 287-300, (1983) · Zbl 0541.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.