{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:45Z","timestamp":1725663165063},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540081388"},{"type":"electronic","value":"9783540373896"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08138-0_1","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T11:17:21Z","timestamp":1330168641000},"page":"1-16","source":"Crossref","is-referenced-by-count":4,"title":["On polynomial time isomorphisms of complete sets"],"prefix":"10.1007","author":[{"given":"L.","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Hartmanis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,23]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Cook, S. \"The Complexity of Theorem Proving Procedures\", Proceedings Third Annual ACM Symposium an Theory of Computing, May 3\u20135, 1971, pp 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Cordova, E., R. Lipton and A.R. Meyer, \"Exponential Tape Complete Problems for Petri Nets and Commutative Semigraphs; Preliminary Report\", Proceedings Eighth Annual ACM Symposium on Theory of Computing, May 3\u20135, 1976, pp. 50\u201354.","DOI":"10.1145\/800113.803630"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Hartmanis, J and L. Berman, \"On Isomorphisms and Density of NP and other Complete Sets,\" Proceedings Eighth Annual ACM Symposium on Theory of Computing, May 3\u20135, 1976, pp 30\u201340.","DOI":"10.1145\/800113.803628"},{"key":"1_CR4","first-page":"1","volume-title":"Advances in Computers, Vol 14","author":"J. Hartmanis","year":"1976","unstructured":"Hartmanis, J. and J. Simon, \"on the Structure of Feasible Computations\", in Advances in Computers, Vol 14 (eds. M. Rubinoff and M.C. Yovits) Academic Press, New York, 1976, pp 1\u201343."},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R. \"Reducabilities Among Combinatorial Problems\", In \"Complexity of Computer Computations\" (R. Miller and J. Thatcher, eds) pp 85\u2013104 Plenum Press New York. 1972."},{"issue":"1","key":"1_CR6","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. E. Ladner","year":"1975","unstructured":"Ladner, R.E. \"On the Structure of Polynomial Time Reducibility\" JACM, vol. 22, No. 1, January 1975, pp. 155\u2013171.","journal-title":"JACM"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Manders, K. and L. Adleman, \"NP-Complete Decision Problems for Quadratic Polynomials,\" Proceeding Eighth Annual ACM Symposium on Theory of Computing, May 3\u20135, 1976 pp. 23\u201329.","DOI":"10.1145\/800113.803627"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Meyer, A.R. and L. Stochmeyer, \"The Equvalence Problem for Regular Expressions with Squaring Requires Exponential Space\", IEEE 13th Annual Symposium on Switching and Automata Theory, 1972, pp. 125\u2013129","DOI":"10.1109\/SWAT.1972.29"},{"key":"1_CR9","unstructured":"Plaisted, D.A. \"More NP-Hard and NP-Complete Problems Involving Polynomials and Integers\", IEEE 17the FOCS, 1976."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J. \"Complexity of Decision Problems Based in Finite Two-Person Perfect-Information Games\", Proceedings Eighth Annual ACM Symposium on Theory of Computing, May 3\u20135, 1976, pp. 41\u201349.","DOI":"10.1145\/800113.803629"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08138-0_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:58:59Z","timestamp":1605625139000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08138-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540081388","9783540373896"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-08138-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}