Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 154))
Included in the following conference series:
135Accesses
Abstract
In this paper we study the computational complexity of sets of different densities inNP. We show that the deterministic computation time for sets inNP can depend on their density if and only if there is a collapse or partial collapse of the corresponding higher nondeterministic and deterministic time bonded complexity classes. We show also that forNP sets of different densities there exist complete sets of the corresponding density under polynomial time Turing reductions. Finally, we show that these results can be interpreted as results about the complexity of theorem proving and proof presentation in axiomatized mathematical systems. This interpretation relates fundamental questions about the complexity of our intellectual tools to basic structural problems aboutP, NP, CoNP, andPSPACE, discussed in this paper.
This research was supported in part by National Science Foundation Grant MCS78-00418. Furthermore, the work of the second author was supported in part by a Dr. Chaim Weizmann Post-Doctoral Fellowship for Scientific Research.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L. Adleman, “Two Theorems on Random Polynomial Time”, IEEE-FOCS Symp. (1978), 75–83.
P. Berman, “Relationship Between Density and Deterministic Complexity ofNP-Complete Languages”, 5th ICALP, Lecture Notes in Computer Science 62, Springer-Verlag, Berlin (1978), 63–71.
L. Berman and J. Hartmanis, “On Isomorphism and Density ofNP and Other Complete Sets”, SIAM J. on Computing (1977), 305–322.
R.V. Book, “Tally Languages and Complexity Classes”, Information and Control 26 (1974), 186–193.
R. Book, C. Wilson, and M. Xu, “Relativizing Time and Space”, IEEE-FOCS Symp. (1981), 254–259.
J. Gill, “Computational Complexity of Probabilistic Turing Machines”, SIAM J. on Computing 6 (1977), 675–695.
J. Hartmanis, “On Sparse Sets in NP-P”, Department of Computer Science, Cornell University, TR82-508, August 1982.
J. Hartmanis, N. Immerman, and V. Sewelson, “Sparse Sets in NP-P: EXPTIME vs NEXP-TIME”, ACM Symposium on Theory of Computing, 1983.
R.M. Karp and R.J. Lipton, “Some Connections Between Nonuniform and Uniform Complexity Classes”, Proceedings 12th Annual ACM Symposium on Theory of Computing (April 1980), 302–309.
S. Mahaney, “Sparse Complete Sets forNP: Solution of a Conjecture of Berman and Hartmanis”, Proceedings 21st IEEE Foundations of Computer Science Symposium (1980), 42–49.
V. Sewelson, private communication.
Author information
Authors and Affiliations
Department of Computer Science, Cornell University, 14853, Ithaca, New York
J. Hartmanis & Y. Yesha
- J. Hartmanis
You can also search for this author inPubMed Google Scholar
- Y. Yesha
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1983 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hartmanis, J., Yesha, Y. (1983). Computation times of NP sets of different densities. In: Diaz, J. (eds) Automata, Languages and Programming. ICALP 1983. Lecture Notes in Computer Science, vol 154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0036918
Download citation
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative