{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:45Z","timestamp":1725663105828},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540078548"},{"type":"electronic","value":"9783540381693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1976]]},"DOI":"10.1007\/3-540-07854-1_183","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T11:12:24Z","timestamp":1330168344000},"page":"255-259","source":"Crossref","is-referenced-by-count":6,"title":["On the relativization of deterministic and nondeterministic complexity classes"],"prefix":"10.1007","author":[{"given":"M. I.","family":"Dekhtyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,21]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0022-0000(74)80008-5","volume":"9","author":"R. Book","year":"1974","unstructured":"Book R., Comparing complexity classes, J. Comp. and Syst. Sci., 1974, 9, 213\u2013229.","journal-title":"J. Comp. and Syst. Sci."},{"key":"27_CR2","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/3-540-07389-2_187","volume":"32","author":"B. A. Trakhtenbrot","year":"1975","unstructured":"Trakhtenbrot B.A., On problems solvable by successive trials, Lect. Notes in Computer Sci., 32, 1975, 125\u2013137.","journal-title":"Lect. Notes in Computer Sci."},{"doi-asserted-by":"crossref","unstructured":"Ladner R., Lynch N., Selman A.L., Comparison of polynomial-time reducibilities, Sixth ACM Symp. on Thery of Computing, 1974, 110\u2013121.","key":"27_CR3","DOI":"10.1145\/800119.803891"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"Savitch W.J., Relationships between nondeterministic and deterministic tape complexities, J.Comp. and Syst. Sci., 1970, 4, 177\u2013192.","journal-title":"J.Comp. and Syst. Sci."},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S. A. Cook","year":"1973","unstructured":"Cook S.A., A hierachy for nondeterministic time complexity, J.Comp. and Syst. Sci., 1973, 7, 343\u2013352.","journal-title":"J.Comp. and Syst. Sci."},{"unstructured":"Valiant L.G., Relate complexity as checing and evaluating, Center of Comput. Studies, University of Lids, 1974.","key":"27_CR6"},{"doi-asserted-by":"crossref","unstructured":"Karp R.M., Reducibility among combinatorial problems, in Complexity of Computer Computations, Miller and Thatcher (eds.),Plenum Press, 1973, 85\u2013103.","key":"27_CR7","DOI":"10.1007\/978-1-4684-2001-2_9"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1976"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-07854-1_183.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:58:34Z","timestamp":1605625114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-07854-1_183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976]]},"ISBN":["9783540078548","9783540381693"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/3-540-07854-1_183","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1976]]}}}