{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:22:10Z","timestamp":1725456130417},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354010027X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022494","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T05:49:12Z","timestamp":1132724952000},"page":"40-57","source":"Crossref","is-referenced-by-count":6,"title":["An essay about research on sparse NP complete sets"],"prefix":"10.1007","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[]},{"given":"S. R.","family":"Mahaney","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley (1974)."},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P. \u201cRelationship Between Density and Deterministic Complexity of NP-Complete Languages,\u201d Fifth Int. Colloquium on Automata, Languages and Programming, Italy (July 1978), Springer-Verlag Lecture Notes in Computer Science Vol. 62, pp. 63\u201371.","DOI":"10.1007\/3-540-08860-1_6"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L. and Hartmanis, J., \u201cOn Isomorphisms and Density of NP and Other Complete Sets,\u201d SIAM J. Comput., 6 (1977), pp. 305\u2013322. See also Proceedings 8th Annual ACM Symposium on Theory of Computing, (1976) pp. 30\u201340.","journal-title":"SIAM J. Comput."},{"key":"3_CR4","unstructured":"Book, R., Wrathall, C., Selman, A., and Dobkin, D., \u201cInclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.\u201d"},{"key":"3_CR5","unstructured":"Cook, S.A., \u201cThe Complexity of Theorem Proving Procedures,\u201d Proc. 3rd Annual ACM Symposium on Theory of Computing, (1977) pp. 151\u2013158."},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Fortune, S., \u201cA Note on Sparse Complete Sets,\u201d SIAM J. Comput., (1979), pp. 431\u2013433.","DOI":"10.1137\/0208034"},{"key":"3_CR7","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., and Johnson, D.S., \u201cComputers and Intractability, A Guide to the Theory of NP-Completeness,\u201d W.H. Freeman and Co., San Francisco, 1979."},{"key":"3_CR8","first-page":"1","volume-title":"Theoretical Computer Science, 3rd GI Conference","author":"J. Hartmanis","year":"1977","unstructured":"Hartmanis, J., and Berman, L., \u201cOn Polynomial Time Isomorphisms of Complete Sets,\u201d Theoretical Computer Science, 3rd GI Conference, March, 1977, Lecture Notes in Computer Science, Vol. 48, Springer-Verlag, Heidelberg, pp. 1\u201315."},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0022-0000(78)90027-2","volume":"16","author":"J. Hartmanis","year":"1978","unstructured":"Hartmanis, J., and Berman, L., \u201cOn Polynomial Time Isomorphisms of Some New Complete Sets,\u201d J. of Computer and System Sciences, Vol. 16 (1978), pp. 418\u2013422.","journal-title":"J. of Computer and System Sciences"},{"key":"3_CR10","unstructured":"Hartmanis, J., and Mahaney, S.R., \u201cOn Census Complexity and Sparseness of NP-Complete Sets,\u201d Department of Computer Science, Cornell University, Technical Report TR 80-416 (April 1980)."},{"key":"3_CR11","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R., \u201cReducibility Among Combinatorial Problems,\u201d in Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.), Plenum, New York (1972)."},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M., and Lipton, R.J., \u201cSome Connections between Nonuniform and Uniform Complexity Classes,\u201d Proc. 12th ACM Symposium on Theory of Computing, (May 1980).","DOI":"10.1145\/800141.804678"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E., \u201cOn the Structure of Polynomial Time Reducibility,\u201d J. Assoc. Computing Machinery, Vol. 22 (1975), pp. 155\u2013171.","journal-title":"J. Assoc. Computing Machinery"},{"key":"3_CR14","unstructured":"Landweber, L.H., Lipton, R.J., and Robertson, E.L., \u201cOn the Structure of Sets in NP and Other Complexity Classes,\u201d Computer Science Tech. Report 342 (December 19\/8), University of Wisconsin-Madison."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Mahaney, S.R., \u201cSparse Complete Sets for NP: Solution of a Conjecture by Berman and Hartmanis,\u201d Department of Computer Science, Cornell University, Technical Report TR 80-417 (April 1980).","DOI":"10.1109\/SFCS.1980.40"},{"key":"3_CR16","unstructured":"Patterson, M, and Meyer, A.R., \u201cWith What Frequency are Apparently Intractable Problems Difficult?\u201d, Laboratory for Computer Science, M.I.T. Tech. Report., February 1979."},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J., \u201cThe Polynomial-Time Hierarchy,\u201d Theoretical Computer Science Vol. 3, (1977), pp. 1\u201322.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1980"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0022494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:21:32Z","timestamp":1586578892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354010027X"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0022494","relation":{},"subject":[]}}