On sparse sets in NP-P. (English) Zbl 0501.68014


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, 2, 305-322, (1977) · Zbl 0356.68059
[2] Book, R.V., Tally languages and complexity classes, Inform. control, 186-193, (1974) · Zbl 0287.68029
[3] Book, R.V.; Wrathall, C.; Selman, A.L.; Dobkin, D., Inclusion-complete tally languages and the hartmanis-berman conjecture, Math. systems theory, 1-8, (1977) · Zbl 0365.68044
[4] Book, R.V.; Wilson, C.B.; Xu, M., Relativizing time and space, Proc. 22nd IEEE foundations of computer science symp., 254-259, (1981)
[5] Garey, M.R.; Johnson, D.S., Computers and intractability, A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[6] Karp, R.M.; Lipton, R.J., Some connections between nonuniform and uniform complexity classes, Proc. 12th ann. ACM symp. on theory of computation, 302-309, (1980)
[7] S. Kurtz, Private communication.
[8] Ladner, R.E., On the structure of polynomial time reducibility, J. ACM, 155-171, (1975) · Zbl 0322.68028
[9] Mahaney, S., Sparse complete sets for NP: solution of a conjecture of berman and hartmanis, Proc. 21st IEEE foundations of computer science symp., 42-49, (1980)
[10] Wilson, C.B., Relativization, reducibilities and the exponential hierarchy, Tech. rept. no. 140/80, (1980), Department of Computer Science, University of Toronto Toronto, Ontario
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.