{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T20:49:22Z","timestamp":1696020562694},"reference-count":44,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1983,12,1]],"date-time":"1983-12-01T00:00:00Z","timestamp":439084800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[1983,12]]},"DOI":"10.1016\/0196-6774(83)90019-6","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"397-411","source":"Crossref","is-referenced-by-count":14,"title":["The NP-completeness column: An ongoing guide"],"prefix":"10.1016","volume":"4","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(83)90019-6_BIB1","series-title":"Proceedings 13th Ann. ACM Symp. on Theory of Computing","first-page":"228","article-title":"Low level complexity for combinatorial games","author":"Adachi","year":"1981"},{"key":"10.1016\/0196-6774(83)90019-6_BIB2","series-title":"Mathmatical Recreations and Essays","author":"Ball","year":"1974"},{"key":"10.1016\/0196-6774(83)90019-6_BIB3","author":"Berlekamp","year":"1982"},{"key":"10.1016\/0196-6774(83)90019-6_BIB4","author":"Berlekamp","year":"1982"},{"key":"10.1016\/0196-6774(83)90019-6_BIB5","unstructured":"F. Berman, F. T. Leighton, P. Shor, and L. Snyder, private communication (1983)."},{"key":"10.1016\/0196-6774(83)90019-6_BIB6","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(83)90019-6_BIB7","series-title":"Proceedings 17th Ann. Symp. on Foundations of Computer Science","first-page":"98","article-title":"Alternation","author":"Chandra","year":"1976"},{"key":"10.1016\/0196-6774(83)90019-6_BIB8","series-title":"Puzzle","author":"Churchill","year":"1893"},{"key":"10.1016\/0196-6774(83)90019-6_BIB9","doi-asserted-by":"crossref","unstructured":"C. J. Colbourn, Embedding partial Steiner triple systems is NP-complete, J. Combinatorial Theory Ser. A, to appear.","DOI":"10.1016\/0097-3165(83)90031-6"},{"key":"10.1016\/0196-6774(83)90019-6_BIB10","doi-asserted-by":"crossref","unstructured":"C. J. Colbourn, The complexity of completing partial Latin squares, Disc. Applied Math., to appear.","DOI":"10.1016\/0166-218X(84)90075-1"},{"key":"10.1016\/0196-6774(83)90019-6_BIB11","series-title":"First Southeast Asian Conf. on Graph Theory","article-title":"The computational complexity of recognizing critical sets","author":"Colbourn","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB12","series-title":"On numbers and games","author":"Conway","year":"1976"},{"key":"10.1016\/0196-6774(83)90019-6_BIB13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0022-0000(76)80048-7","article-title":"Storage requirements for deterministic polynomial time recognizable languages","volume":"13","author":"Cook","year":"1976","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(83)90019-6_BIB14","series-title":"The Way to Play","year":"1977"},{"key":"10.1016\/0196-6774(83)90019-6_BIB15","series-title":"Proceedings 15th Ann. ACM Symp. on Theory of Computing","first-page":"152","article-title":"On the diameter of permutation groups","author":"Driscoll","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB16","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0097-3165(81)90016-9","article-title":"Computing a perfect strategy for n \u00d7 n chess requires time exponential in n","volume":"31","author":"Fraenkel","year":"1981","journal-title":"J. Combinatorial Theory Ser. A"},{"key":"10.1016\/0196-6774(83)90019-6_BIB17","unstructured":"M. Furst, private communication (1983)."},{"key":"10.1016\/0196-6774(83)90019-6_BIB18","series-title":"The Scientific American Book of Mathematical Puzzles and Diversions","author":"Gardner","year":"1959"},{"key":"10.1016\/0196-6774(83)90019-6_BIB19","series-title":"New Mathematical Diversions from Scientific American","author":"Gardner","year":"1966"},{"key":"10.1016\/0196-6774(83)90019-6_BIB20","series-title":"The Sixth Book of Mathematical Games from Scientific American","author":"Gardner","year":"1971"},{"key":"10.1016\/0196-6774(83)90019-6_BIB21","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0209038","article-title":"The pebbling problem is complete for polynomial space","volume":"9","author":"Gilbert","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90019-6_BIB22","series-title":"PSPACE-hardness of the motion planning problem for rectangular objects","author":"Hopcroft","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB23","series-title":"Formal Languages and their Relation to Automata","author":"Hopcroft","year":"1969"},{"key":"10.1016\/0196-6774(83)90019-6_BIB24","first-page":"4","article-title":"Blindfold games are harder than games with perfect information","volume":"6","author":"Jones","year":"1978","journal-title":"Bulletin of the European Assoc. for Theoretical Comput. Sci."},{"key":"10.1016\/0196-6774(83)90019-6_BIB25","series-title":"Proceedings 22nd Ann. Symp. on Foundations of Computer Science","first-page":"185","article-title":"The complexity of distributed concurrency control","author":"Kanellakis","year":"1981"},{"key":"10.1016\/0196-6774(83)90019-6_BIB26","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1137\/0208046","article-title":"Classes of pebble games and complete problems","volume":"8","author":"Kasai","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90019-6_BIB27","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0022-0000(80)90033-1","article-title":"The complexity of problems in systems of communicating sequential processes","volume":"21","author":"Ladner","year":"1980","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(83)90019-6_BIB28","series-title":"Black-white pebbles and graph separation","author":"Lengauer","year":"1980"},{"key":"10.1016\/0196-6774(83)90019-6_BIB29","series-title":"Proceedings 24th Ann. Symp. on Foundations of Computer Science","article-title":"Games against nature","author":"Papadimitriou","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB30","series-title":"Press-Ups is PSPACE complete","author":"Peterson","year":"1979"},{"key":"10.1016\/0196-6774(83)90019-6_BIB31","series-title":"Proceedings 20th Ann. Symp. on Foundations of Computer Science","first-page":"348","article-title":"Multiple-person alternation","author":"Peterson","year":"1979"},{"key":"10.1016\/0196-6774(83)90019-6_BIB32","series-title":"Proceedings 11th Ann. ACm Symp. on Theory of Computing","first-page":"288","article-title":"Universal games of incomplete information","author":"Reif","year":"1979"},{"key":"10.1016\/0196-6774(83)90019-6_BIB33","doi-asserted-by":"crossref","unstructured":"J. H. Reif, The complexity of two player games of incomplete information, J. Comput. System Sci., to appear.","DOI":"10.1016\/0022-0000(84)90034-5"},{"key":"10.1016\/0196-6774(83)90019-6_BIB34","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF00288536","article-title":"Gobang ist PSPACE-vollst\u00e4ndig","volume":"13","author":"Reisch","year":"1980","journal-title":"Acta Inform."},{"key":"10.1016\/0196-6774(83)90019-6_BIB35","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00288964","article-title":"Hex ist PSPACE-vollst\u00e4ndig","volume":"15","author":"Reisch","year":"1981","journal-title":"Acta Inform."},{"key":"10.1016\/0196-6774(83)90019-6_BIB36","doi-asserted-by":"crossref","unstructured":"J. M. Robson, N by N Checkers is Exptime-complete, SIAM J. Comput., to appear.","DOI":"10.1137\/0213018"},{"key":"10.1016\/0196-6774(83)90019-6_BIB37","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","article-title":"Complete register allocation problems","volume":"4","author":"Sethi","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90019-6_BIB38","article-title":"On the combinatorial complexity of motion coordination","author":"Spirakis","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB39","series-title":"Strong NP-hardness of moving many discs","author":"Spirakis","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB40","series-title":"Moving many pebbles in a graph is polynomial time","author":"Spirakis","year":"1983"},{"key":"10.1016\/0196-6774(83)90019-6_BIB41","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0208013","article-title":"Provably difficult combinatorial games","volume":"8","author":"Stockmeyer","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90019-6_BIB42","series-title":"On the complexity of chess","author":"Storer","year":"1979"},{"key":"10.1016\/0196-6774(83)90019-6_BIB43","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"8","author":"Valiant","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(83)90019-6_BIB44","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","article-title":"Graphs, puzzles, homotopy, and the alternating group","volume":"16","author":"Wilson","year":"1974","journal-title":"J. Combinatorial Theory Ser. B"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677483900196?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677483900196?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T06:50:49Z","timestamp":1548744649000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677483900196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["0196677483900196"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(83)90019-6","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}