×

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


MSC:

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
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass
[2] Berman, L.; Hartmanis, J., (Proceedings Eighth Annual ACM Symposium on Theory of Computing (May 1976)), 30-40 · Zbl 0356.68059
[3] Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (Fifth International Colloquium on Automata, Languages, and Programming. Fifth International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 62 (1978), Springer-Verlag: Springer-Verlag Berlin), 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, (Proceedings, 3rd Annual ACM Symposium on Theory of Computing (1971)), 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., 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: Addison-Wesley Reading, Mass · Zbl 0426.68001
[11] Karp, R., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-103 · Zbl 0366.68041
[12] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (Proceedings, 12th ACM Symposium on Theory of Computing (May 1980)), 302-309
[13] T. Long, “A Note on Cosparse Polynomial Time Turing Complete Sets for NP,” to appear.; T. Long, “A Note on Cosparse Polynomial Time Turing Complete Sets for NP,” to appear.
[14] Mahaney, S., Sparse NP-Complete Sets, (Ph. D. Thesis (1981), Cornell University) · 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, (Proceedings, 13th Annual Symposium on Switching and Automata Theory. Proceedings, 13th Annual Symposium on Switching and Automata Theory, California (1972), IEEE Computer Society), 125-129
[17] Simon, J., On the difference between one and many, (Fourth International Colloquium on Automata, Languages, and Programming. Fourth International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 52 (1977), Springer-Verlag: Springer-Verlag Berlin), 480-491
[18] J. Simon and S. Mahaney, to appear.; J. 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. 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.