{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:47:53Z","timestamp":1764557273965,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T00:00:00Z","timestamp":1355875200000},"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":["SIGACT News"],"published-print":{"date-parts":[[2012,12,19]]},"abstract":"<jats:p>Heuristic approaches often do so well that they seem to pretty much always give the right answer. How close can heuristic algorithms get to always giving the right answer, without inducing seismic complexity-theoretic consequences? This article first discusses how a series of results by Berman, Buhrman, Hartmanis, Homer, Longpr\u00e9, Ogiwara, Sch\u00f6ning, and Watanabe, from the early 1970s through the early 1990s, explicitly or implicitly limited how well heuristic algorithms can do on NP-hard problems. In particular, many desirable levels of heuristic success cannot be obtained unless severe, highly unlikely complexity class collapses occur. Second, we survey work initiated by Goldreich and Wigderson, who showed how under plausible assumptions deterministic heuristics for randomized computation can achieve a very high frequency of correctness. Finally, we consider formal ways in which theory can help explain the effectiveness of heuristics that solve NP-hard problems in practice.<\/jats:p>","DOI":"10.1145\/2421119.2421135","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"70-89","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["SIGACT News Complexity Theory Column 76"],"prefix":"10.1145","volume":"43","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704440107"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_12"},{"volume-title":"Bulletin of the EATCS","year":"2012","author":"Barak B.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646830.707695"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.21"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369156"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334214"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875605"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.01.002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455518.1455522"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01929-6_6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1771668.1771691"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02777-2_9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.026"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000378.2000406"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/369836.369838"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206049"},{"volume-title":"Freeman and Company","year":"1979","author":"Garey M.","key":"e_1_2_1_23_1"},{"volume-title":"Handbook of Knowledge Representation. Elsevier","year":"2008","author":"Gomes C.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30891-8_15"},{"key":"e_1_2_1_26_1","first-page":"431","volume-title":"Proceedings of the 15th National Conference on Artificial Intelligence","author":"Gomes C.","year":"1998"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646978.711713"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"A. Haken. The intractability of resolution. Theoretical Computer Science 39(2--3):297--308 1985.  A. Haken. The intractability of resolution. Theoretical Computer Science 39(2--3):297--308 1985.","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"J. Hartmanis N. Immerman and V. Sewelson. Sparse sets in NP?P: EXPTIME versus NEXPTIME. Information and Control 65(2--3):159--181 1985.  J. Hartmanis N. Immerman and V. Sewelson. Sparse sets in NP?P: EXPTIME versus NEXPTIME. Information and Control 65(2--3):159--181 1985.","DOI":"10.1016\/S0019-9958(85)80004-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80006-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/645714.664953"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1992.215396"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/829497.829786"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.34"},{"key":"e_1_2_1_36_1","first-page":"231","volume-title":"Sixth International Conference on Theory and Applications of Satisfiability Testing (informal proceedings)","author":"Interian Y.","year":"2003"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_32"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0019-z"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"e_1_2_1_44_1","first-page":"63","volume-title":"Studies in Complexity Theory","author":"Mahaney S.","year":"1986"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703438629"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220030"},{"key":"e_1_2_1_47_1","unstructured":"C. Papadimitriou. Computational Complexity. Addison Wesley 1994.  C. Papadimitriou. Computational Complexity. Addison Wesley 1994."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622591.1622596"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972640"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01704904"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1203350879"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1814370.1814389"},{"key":"e_1_2_1_54_1","first-page":"363","volume-title":"Proceedings of the 23rd AAAI Conference on Artificial Intelligence","author":"Samer M.","year":"2008"},{"key":"e_1_2_1_55_1","unstructured":"L. Trevisan. Lecture notes on computational complexity. www.cs.berkeley.edu\/\u00bfluca\/notes\/complexitynotes02.pdf (Lecture 12) 2002.  L. Trevisan. Lecture notes on computational complexity. www.cs.berkeley.edu\/\u00bfluca\/notes\/complexitynotes02.pdf (Lecture 12) 2002."},{"volume-title":"Springer","year":"2001","author":"Vanderbei R.","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1630659.1630827"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622673.1622687"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212027"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/141914.141921"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0243-3"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421119.2421135","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2421119.2421135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:34Z","timestamp":1750234714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421119.2421135"}},"subtitle":["an atypical survey of typical-case heuristic algorithms"],"short-title":[],"issued":{"date-parts":[[2012,12,19]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12,19]]}},"alternative-id":["10.1145\/2421119.2421135"],"URL":"https:\/\/doi.org\/10.1145\/2421119.2421135","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2012,12,19]]},"assertion":[{"value":"2012-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}