Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. (English) Zbl 0493.68043


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI Link


[1] Aho, A.; Hopcroft, J.; Ullman, J., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass
[2] Berman, L.; Hartmanis, J.; Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, (), 6, 30-40, (1977) · Zbl 0356.68059
[3] Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (), 63-71
[4] Book, R.; Wrathall, C.; Selman, A.; Dobkin, D., Inclusion complete tally languages and the hartmanis-berman conjecture, Math. systems theory, 11 (, 1-8, (1977) · Zbl 0365.68044
[5] Cook, S., The complexity of theorem proving procedures, (), 151-158
[6] Fortune, S., A note on sparse complete sets, SIAM. J. comput., 8, 431-433, (1979) · Zbl 0415.68006
[7] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. comput., 6, 675-695, (1977) · Zbl 0366.02024
[8] Hartmanis, J.; Mahaney, S., On census complexity and sparseness of NP-complete sets, Cornell university, computer science department technical report TR 80-416, Ithaca. New York, (April 1980)
[9] Hartmanis, J.; Mahaney, S.; Hartmanis, J.; Mahaney, S., An essay about research on sparse NP-complete sets, (), Cornell university, department of computer science technical report TR 80-244, (1980) · Zbl 0444.68032
[10] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, Mass · Zbl 0426.68001
[11] Karp, R., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[12] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (), 302-309
[13] {\scT. Long}, “A Note on Cosparse Polynomial Time Turing Complete Sets for NP,” to appear.
[14] Mahaney, S., Sparse NP-complete sets, () · Zbl 0444.68032
[15] Meyer, A.; Paterson, M., With what frequency are apparently intractable problems difficult?, MIT technical report, (February 1979)
[16] Meyer, A.; Stockmeyer, L., The equivalence problem for regular expressions with squaring requires exponential time, (), 125-129
[17] Simon, J., On the difference between one and many, (), 480-491
[18] {\scJ. Simon and S. Mahaney}, to appear.
[19] Stockmeyer, L., The polynomial time hierarchy, Theoret. comput. sci., 3, 1-22, (1976) · Zbl 0353.02024
[20] Valiant, L., On the complexity of computing the permanent, Theoret. comput. sci., 8, 189-202, (1979) · Zbl 0415.68008
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.