{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:21:05Z","timestamp":1725456065638},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540557890"},{"type":"electronic","value":"9783540472858"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/bfb0023781","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T05:11:10Z","timestamp":1132377070000},"page":"353-366","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Completeness for NP via projection translations"],"prefix":"10.1007","author":[{"given":"Iain A.","family":"Stewart","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"28_CR1","volume-title":"Model Theory","author":"C.C. Chang","year":"1977","unstructured":"C.C.Chang, H.J.Keisler: Model Theory, North-Holland, Amsterdam, 1977."},{"key":"28_CR2","first-page":"357","volume-title":"Lecture Notes in Computer Science 171","author":"E. Dahlhaus","year":"1979","unstructured":"E.Dahlhaus: Reduction to NP-complete problems by interpretations, Lecture Notes in Computer Science 171, Berlin: Springer-Verlag, 1979, 357\u2013365."},{"key":"28_CR3","unstructured":"R.Fagin: Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation (Ed. R.Karp), SIAM-AMS Proc, 7, 1974, 27\u201341."},{"key":"28_CR4","volume-title":"Computers and intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R.Garey and D.S.Johnson: Computers and intractability, W.H.Freeman and Co., San Francisco, 1979."},{"key":"28_CR5","first-page":"175","volume-title":"Lecture Notes in Mathematics 1104","author":"Y. Gurevich","year":"1984","unstructured":"Y.Gurevich: Toward logic tailored for computational complexity, Computation and Proof Theory (Ed. E.B\u00f6rger et al.), Lecture Notes in Mathematics 1104, Berlin: Springer-Verlag, 1984, 175\u2013216."},{"key":"28_CR6","unstructured":"Y.Gurevich: Logic and the challenge of computer science, in: Current Trends in Theoretical Computer Science (Ed. E. B\u00f6rger), Computer Science Press, 1987, 1\u201357."},{"issue":"4","key":"28_CR7","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N.Immerman: Languages that capture complexity classes, SIAM J. Comput., 16, 4, 1987, 760\u2013778.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"28_CR8","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N.Immerman: Nondeterministic space is closed under complementation, SIAM J. Comput., 17, 5, 1988, 935\u2013938.","journal-title":"SIAM J. Comput."},{"key":"28_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R.M. Karp","year":"1972","unstructured":"R.M.Karp, Reducibility among combinatorial problems, Complexity of computer computations (Ed. R.E.Miller and J.W.Thatcher), Plenum Press, New York, 1972, 85\u2013103."},{"key":"28_CR10","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1002\/malq.19770233608","volume":"23","author":"L. Lovasz","year":"1977","unstructured":"L.Lovasz and P.Gacs: Some remarks on generalized spectra, Zeitschr. f. math., Logik und Grundlagen d. Math., 23, 1977, 547\u2013554.","journal-title":"Zeitschr. f. math., Logik und Grundlagen d. Math."},{"key":"28_CR11","volume-title":"Introduction to Algorithms: a creative approach","author":"U. Manber","year":"1989","unstructured":"U.Manber: Introduction to Algorithms: a creative approach, Addison-Wesley, Reading, Mass. 1989."},{"key":"28_CR12","volume-title":"Proc. TURING 1990: A colloquium in celebration of Alan Turing","author":"I.A. Stewart","year":"1990","unstructured":"I.A.Stewart: The demise of the Turing machine in complexity theory, Proc. TURING 1990: A colloquium in celebration of Alan Turing, Brighton, England, April, 1990, Oxford Univ. Press, to appear."},{"key":"28_CR13","unstructured":"I.A.Stewart: Using the Hamiltonian operator to capture NP, to appear, J. Comput. System Sci."},{"issue":"3","key":"28_CR14","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1093\/logcom\/1.3.305","volume":"1","author":"I.A. Stewart","year":"1991","unstructured":"I.A.Stewart: Comparing the expressibility of languages formed using NP-complete operators, J. Logic Computat., 1, 3, 1991, 305\u2013330.","journal-title":"J. Logic Computat."},{"key":"28_CR15","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0020-0190(91)90121-W","volume":"40","author":"I.A. Stewart","year":"1991","unstructured":"I.A.Stewart: Complete problems for symmetric logspace involving free groups, Inform. Process. Lett., 40, 1991, 263\u2013267.","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:05:37Z","timestamp":1558256737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557890","9783540472858"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0023781","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}