{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T17:58:09Z","timestamp":1791136689642,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540108436","type":"print"},{"value":"9783540387459","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10843-2_23","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:27:56Z","timestamp":1330190876000},"page":"278-293","source":"Crossref","is-referenced-by-count":6,"title":["Computing a perfect strategy for n\u00d7n chess requires time exponential in n"],"prefix":"10.1007","author":[{"given":"Aviezri S.","family":"Fraenkel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Lichtenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"A.S. Fraenkel, M.R. Garey, D.S. Johnson, T. Schaefer and Y. Yesha, The complexity of checkers on an n\u00d7n board \u2014 preliminary report, Proc. 19th Annual Symp. on Foundations of Computer Science, 55\u201364, Ann Arbor, MI, October 1978; IEEE Computer Society, Long Beach, CA, 1978.","DOI":"10.1109\/SFCS.1978.36"},{"key":"23_CR2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979."},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1145\/322186.322201","volume":"27","author":"D. Lichtenstein","year":"1980","unstructured":"D. Lichtenstein and M. Sipser, Go is Polynomial-Space hard, J. ACM 27 (1980), 393\u2013401. Also appeared in Proc. 19th Annual Symp. on Foundations of Computer Science, 48\u201354, Ann Arbor, MI, October 1978; IEEE Computer Society, Long Beach, CA, 1978.","journal-title":"J. ACM"},{"key":"23_CR4","volume-title":"Official Rules of Chess","year":"1978","unstructured":"M.E. Morrison, editor, Official Rules of Chess, 2nd ed., David McKay, New York, 1978.","edition":"2nd ed."},{"key":"23_CR5","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF00288536","volume":"13","author":"S. Reisch","year":"1980","unstructured":"S. Reisch, Gobang ist PSPACE-vollst\u00e4ndig, Acta Inform. 13 (1980), 59\u201366.","journal-title":"Acta Inform."},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00288964","volume":"15","author":"S. Reisch","year":"1981","unstructured":"S. Reisch, Hex ist PSPACE-vollst\u00e4ndig, Acta Inform. 15 (1981), 167\u2013191.","journal-title":"Acta Inform."},{"key":"23_CR7","unstructured":"J.M. Robson, N by N chess is Pspace-hard, TR-CS-80-09, Computer Science Dept., Australian National University, 1980."},{"key":"23_CR8","unstructured":"H. Samelson, editor, Queries, No. 4 (iii), Notices Amer. Math. Soc. 24 (1977), 190\u2013191."},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0208013","volume":"8","author":"L. J. Stockmeyer","year":"1979","unstructured":"L.J. Stockmeyer and A.K. Chandra, Provably difficult combinatorial games, SIAM J. Comput. 8 (1979), 151\u2013174.","journal-title":"SIAM J. Comput."},{"key":"23_CR10","unstructured":"J. Storer, A note on the complexity of chess, Proc. 1979 Conference on Information Sciences and Systems, Dept. of Electr. Eng., Johns Hopkins University, Baltimore, 160\u2013166."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10843-2_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:03:36Z","timestamp":1605643416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10843-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108436","9783540387459"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-10843-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981]]}}}