×
Hartmanis, Juris

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

Inf. Process. Lett. 16, 55-60 (1983).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0501.68014

Cited in 4 Reviews
Cited in 23 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity

Keywords:

deterministic and nondeterministic computations; exptime; nexptime; expspace
PDFBibTeX XMLCite
\textit{J. Hartmanis}, Inf. Process. Lett. 16, 55--60 (1983; Zbl 0501.68014)
Full Text: DOI

References:

[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: 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.; 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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.