{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:52:43Z","timestamp":1775281963406,"version":"3.50.1"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            This is the 26th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book \u201cComputers and Intractability: A Guide to the Theory of NP-Completeness,\u201d W. H. Freeman &amp; Co., New York, 1979, hereinafter referred to as \u201c[G&amp;J].\u201d Previous columns, the first 23 of which appeared in\n            <jats:italic>J. Algorithms<\/jats:italic>\n            , will be referred to by a combination of their sequence number and year of appearance, e.g., \u201cColumn 1 [1981].\u201d Full bibliographic details on the previous columns, as well as downloadable unofficial versions of them, can be found at http:\/\/www.research.att.com\/~dsj\/columns\/. This column discusses the question of whether finding an object can be computationally difficult even when we know that the object exists.\n          <\/jats:p>","DOI":"10.1145\/1240233.1240247","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["The NP-completeness column"],"prefix":"10.1145","volume":"3","author":[{"given":"David S.","family":"Johnson","sequence":"first","affiliation":[{"name":"AT&amp;T Labs---Research, Florham Park, New Jersey"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_10"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380755"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 118--126","author":"Blum M."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456868"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.30"},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. TR05-134, Electronic Colloquium on Computational Complexity.","author":"Chen X.","year":"2005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_43"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.69"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.20"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.51.1.105"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_14_1","volume-title":"Ed. DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume":"13","author":"Condon A.","year":"1993"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Daskalakis C. Goldberg P. W. and Papadimitriou C. H. 2007. The complexity of computing a Nash equilibrium. Submitted journal version of Daskalakis et al. {2006} Goldberg and Papadimitriou {2006} and Dasakalakis and Papadimitriou {2005}.  Daskalakis C. Goldberg P. W. and Papadimitriou C. H. 2007. The complexity of computing a Nash equilibrium. Submitted journal version of Daskalakis et al. {2006} Goldberg and Papadimitriou {2006} and Dasakalakis and Papadimitriou {2005}.","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. TR05-139, Electronic Colloquium on Computational Complexity.","author":"Daskalakis C.","year":"2005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Englert M."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00018-X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90199-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90216-V"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11758471_36"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132526"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846269"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00152-6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(88)90012-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00068-0"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.79.8.2554"},{"key":"e_1_2_1_32_1","volume-title":"Local Search in Combinatorial Optimization","author":"Johnson D. S."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_34_1","unstructured":"Juba B. 2005. On the hardness of simple stochastic games. M.S. Thesis Carnegie-Mellon University. Currently available from http:\/\/people.csail.mit.edu\/bjuba\/.  Juba B. 2005. On the hardness of simple stochastic games. M.S. Thesis Carnegie-Mellon University. Currently available from http:\/\/people.csail.mit.edu\/bjuba\/."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109571"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-41-00838-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580616"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_40_1","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Dokl. Akad. Nauk. SSSR"},{"key":"e_1_2_1_41_1","unstructured":"Klee V. and Minty G. J. 1972. How good is the simplex algorithm? In Inequalities III O. Shisha Ed. Academic Press New York 159--175.  Klee V. and Minty G. J. 1972. How good is the simplex algorithm? In Inequalities III O. Shisha Ed. Academic Press New York 159--175."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1100"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63481"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.11.7.681"},{"key":"e_1_2_1_45_1","volume-title":"Development of the Number Field Sieve. Lecture Notes in Mathematics","volume":"1554","author":"Lenstra A. K."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_47_1","volume-title":"Lecture Notes in Computer Science","volume":"2976","author":"Lipton R. J."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_49_1","unstructured":"Lueker G. 1976. Manuscript Princeton University.  Lueker G. 1976. Manuscript Princeton University."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_2_1_52_1","unstructured":"Morioka T. 2001. The classification of search problems and their definability in bounded arithmetic. M.S. thesis University of Toronto. Also available as Tech. Rep. TR01-82 Electronic Colloquium on Computational Complexity.  Morioka T. 2001. The classification of search problems and their definability in bounded arithmetic. M.S. thesis University of Toronto. Also available as Tech. Rep. TR01-82 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89602"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221030"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100274"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.3.434"},{"key":"e_1_2_1_59_1","first-page":"1473","article-title":"A tale of two sieves","volume":"43","author":"Pomerance C.","year":"1996","journal-title":"Amer. Math. Soc. Not."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204018"},{"key":"e_1_2_1_61_1","unstructured":"Puri A. 1995. Theory of hybrid systems and discrete event systems. Ph.D. thesis University of California Berkeley.   Puri A. 1995. Theory of hybrid systems and discrete event systems. Ph.D. thesis University of California Berkeley."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220004"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_65_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th International Colloquium on Automata, Languages and Programming","author":"Sipser M."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02940617"},{"key":"e_1_2_1_67_1","volume-title":"Proceedings of the 2nd Algorithms and Complexity in Durham Workshop, H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds. Kings College Publications","author":"V\u00f6cking B.","year":"2006"},{"key":"e_1_2_1_68_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computing","author":"Yannakakis M."},{"key":"e_1_2_1_69_1","volume-title":"Local Search in Combinatorial Optimization","author":"Yannakakis M."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240247"}},"subtitle":["Finding needles in haystacks"],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":70,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240247"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240247","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}