{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:11:51Z","timestamp":1725459111528},"publisher-location":"Berlin\/Heidelberg","reference-count":11,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540123172"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0036918","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T17:38:14Z","timestamp":1138210694000},"page":"319-330","source":"Crossref","is-referenced-by-count":3,"title":["Computation times of NP sets of different densities"],"prefix":"10.1007","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Yesha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"L. Adleman, \u201cTwo Theorems on Random Polynomial Time\u201d, IEEE-FOCS Symp. (1978), 75\u201383.","DOI":"10.1109\/SFCS.1978.37"},{"key":"26_CR2","first-page":"63","volume-title":"5th ICALP, Lecture Notes in Computer Science 62","author":"P. Berman","year":"1978","unstructured":"P. Berman, \u201cRelationship Between Density and Deterministic Complexity of NP-Complete Languages\u201d, 5th ICALP, Lecture Notes in Computer Science 62, Springer-Verlag, Berlin (1978), 63\u201371."},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"L. Berman and J. Hartmanis, \u201cOn Isomorphism and Density of NP and Other Complete Sets\u201d, SIAM J. on Computing (1977), 305\u2013322.","DOI":"10.1137\/0206023"},{"key":"26_CR4","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R.V. Book","year":"1974","unstructured":"R.V. Book, \u201cTally Languages and Complexity Classes\u201d, Information and Control 26 (1974), 186\u2013193.","journal-title":"Information and Control"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"R. Book, C. Wilson, and M. Xu, \u201cRelativizing Time and Space\u201d, IEEE-FOCS Symp. (1981), 254\u2013259.","DOI":"10.1109\/SFCS.1981.39"},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill, \u201cComputational Complexity of Probabilistic Turing Machines\u201d, SIAM J. on Computing 6 (1977), 675\u2013695.","journal-title":"SIAM J. on Computing"},{"key":"26_CR7","unstructured":"J. Hartmanis, \u201cOn Sparse Sets in NP-P\u201d, Department of Computer Science, Cornell University, TR82-508, August 1982."},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, N. Immerman, and V. Sewelson, \u201cSparse Sets in NP-P: EXPTIME vs NEXP-TIME\u201d, ACM Symposium on Theory of Computing, 1983.","DOI":"10.1145\/800061.808769"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"R.M. Karp and R.J. Lipton, \u201cSome Connections Between Nonuniform and Uniform Complexity Classes\u201d, Proceedings 12th Annual ACM Symposium on Theory of Computing (April 1980), 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"S. Mahaney, \u201cSparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis\u201d, Proceedings 21st IEEE Foundations of Computer Science Symposium (1980), 42\u201349.","DOI":"10.1109\/SFCS.1980.40"},{"key":"26_CR11","unstructured":"V. Sewelson, private communication."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0036918.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:21:34Z","timestamp":1607552494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0036918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540123172"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/bfb0036918","relation":{},"subject":[]}}