Abstract
We consider two setsA andB to be close to each other if the census of their symmetric difference,A ▵B, is a slowly increasing function (e.g. a polynomial.) The classes of sets which are polynomially close to some set in a complexity classC (likeP) are studied and characterized. We investigate the question whether complete sets forNP or EXPTIME can be polynomially close to a set inP. Some of the obtained results strengthen or generalize results by Yesha [24], e.g. it is shown that no EXPTIME-hard set can be polynomially close to any set inP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adleman, L. and K. Manders, Reductions that lie, 20th IEEE Sympos. onFoundations of Computer Science, 1979, 397–410.
Balcázar, J., Book, R. and U. Schöning, Sparse oracles, lowness and highness,Math. Foundations of Computer Science, Springer Lecture Notes in Computer Science 176, 1984, 185–193.
Balcázar, J. and U. Schöning, Bi-immune sets for complexity classes,Math. Systems Theory 18 (1985), 1–10.
Bennett, C. H. and J. Gill, Relative to a random oracleA, P A ≠ NPA ≠ coNP A with probability 1,SIAM Journal on Comput. 10 (1981), 96–113.
Berman, L. and J. Hartmanis, On isomorphisms and density ofNP and other complete sets,SIAM Journal on Comput. 6 (1977), 305–327.
Heller, H., On relativized polynomial hierarchies extending two levels, Conference on Computational Complexity Theory, Santa Barbara, March 1983, 109–114.
Huynh, D. T., Some observations about the randomness of hard problems, Technical Report 85-5, Department of Computer Science, Iowa State University, Ames, Iowa 50011, February 1985.
Kannan, R., Circuit-size lower bounds and nonreducibility to sparse sets,Information and Control 55 (1982), 40–56.
Karp, R. M. and R. J. Lipton, Some connections between non-uniform and uniform complexity classes, Proc. of the 12th ACM Sympos. onTheory of Computing, 1980, 302–309.
Lerman, M.,Degrees of Unsolvability, Springer-Verlag, 1983.
Long, T. J., A note on sparse oracles forNP, Journal of Comput. and Syst. Sci. 24 (1982), 224–232.
Long, T. J., Strong nondeterministic polynomial-time reducibilities,Theor. Comput. Sci. 21 (1982), 1–25.
Mahaney, S., Sparse complete sets forNP: solution of a conjecture of Berman and Hartmanis,Journal of Comput. and System Sci. 25 (1985), 130–143.
Meyer, A. and M. Paterson, With what frequency are apparently intractable problems difficult?, MIT technical report TM-126, 1979.
Meyer, A. R. and C. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space,Proc. 13th IEEE Symp. Switch. Autom. Theory (1972), 125–129.
Rogers, H.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
Sacks, G. E.,Degrees of Unsolvability, Princeton University Press, 1963.
Schöning, U., A low and a high hierarchy withinNP, Journal of Comput. and System Sci. 27 (1983), 14–28.
Selman, A. L., Reductions onNP andp-selective sets,Theor. Comput. Sci. 19 (1982), 287–304.
Selman, A. L., Polynomial time enumeration reducibility,Theor. Comput. Sci. 14 (1978), 91–101.
Stockmeyer, L. J., The polynomial-time hierarchy,Theor. Comput. Sci. 3 (1977), 1–22.
Wilson, C. B., Relativized circuit complexity,24th. IEEE Sympos. on Found. of Comput. Sci., 1983, 329–334.
Yao, A. C., On theory and application of trapdoor functions,Proc. 23rd Sympos. on Found. of Comput. Sci., 1982, 80–91.
Yesha, Y., On certain polynomial-time truth-table reducibilities of complete sets to sparse sets,SIAM Journal on Comput. 12 (1983), 411–425.
Young, P., Some structural properties of polynomial reducibilities and sets inNP, Proc. 15th ACM Sympos. Theory of Computing, 1983, 392–401.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Schöning, U. Complete sets and closeness to complexity classes. Math. Systems Theory 19, 29–41 (1986). https://doi.org/10.1007/BF01704904
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01704904