{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:34Z","timestamp":1725662854156},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540107040"},{"type":"electronic","value":"9783540386612"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10704-5_13","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:14:15Z","timestamp":1330190055000},"page":"152-158","source":"Crossref","is-referenced-by-count":0,"title":["On polynomial time computable problems"],"prefix":"10.1007","author":[{"given":"T.","family":"Kasai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Adachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"13_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ullman. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"A. K. Chandra and L. J. Stockmeyer, Alternation, Proc. 17th Ann. IEEE Symp. on Foundation of Computer Sciences, 1976, pp.98\u2013108.","DOI":"10.1109\/SFCS.1976.4"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem-proving procedures, Proc. 3rd ACM Symp. on Theory of Computing, 1971, pp.151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"13_CR4","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1145\/321978.321989","volume":"23","author":"S. Even","year":"1976","unstructured":"S. Even and R. R. Tarjan, A combinatorial problem which is complete in polynomial space, J. Assc. Comput. Mach., 23(1976), pp.710\u2013719.","journal-title":"J. Assc. Comput. Mach."},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"W. D. Jones","year":"1977","unstructured":"W. D. Jones and W. T. Laaser, Complete problems for deterministic polynomial time, Theoretical Comput. Sci., 3(1977), pp.105\u2013117.","journal-title":"Theoretical Comput. Sci."},{"key":"13_CR6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems, Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp.85\u2013104."},{"key":"13_CR7","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1137\/0208046","volume":"8","author":"T. Kasai","year":"1979","unstructured":"T. Kasai, A. Adachi and S. Iwata, Classes of pebble games and complete problems, SIAM J. Comput. 8(1979) pp.574\u2013586.","journal-title":"SIAM J. Comput."},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-0000(80)90001-X","volume":"20","author":"T. Kasai","year":"1980","unstructured":"T. Kasai and A. Adachi, A characterization of time complexity by simple loop programs, J. Comput. System Sci., 20(1980) pp.1\u201317.","journal-title":"J. Comput. System Sci."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer, Complexity of decision problems based on finite two-person perfect-information games, Proc. 8th Ann. ACM Symp. on Theory of Computing, 1976, pp.41\u201349.","DOI":"10.1145\/800113.803629"}],"container-title":["Lecture Notes in Computer Science","Graph Theory and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10704-5_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:38:46Z","timestamp":1619555926000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10704-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540107040","9783540386612"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-10704-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}