{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T06:54:56Z","timestamp":1784357696217,"version":"3.55.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,5,24]],"date-time":"2017-05-24T00:00:00Z","timestamp":1495584000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Alexander vonHumboldt Foundation and NSF","award":["1017597"],"award-info":[{"award-number":["1017597"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-1213151 and CCF-0947262"],"award-info":[{"award-number":["CCF-1213151 and CCF-0947262"]}]},{"DOI":"10.13039\/501100004442","name":"National Science Centre","doi-asserted-by":"crossref","award":["N206 567140"],"award-info":[{"award-number":["N206 567140"]}],"id":[{"id":"10.13039\/501100004442","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001870","name":"Foundation for Polish Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NWO project \u201cSpace and Time Efficient Structural Improvements of Dynamic Programming Algorithms.\u201d"},{"name":"Grant-in-Aid for Scientific Research from Japan Society for the Promotion of Science"},{"name":"ERC Starting Grant PARAMTIGHT","award":["280152"],"award-info":[{"award-number":["280152"]}]},{"name":"ONR Young Investigator award when at the University at Maryland"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"\n The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G\n raph<\/jats:sc>\n C\n oloring<\/jats:sc>\n , H\n amiltonian<\/jats:sc>\n P\n ath<\/jats:sc>\n , D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n , and 3-CNF-S\n at<\/jats:sc>\n . In some instances, improving these algorithms further seems to be out of reach. The CNF-S\n at<\/jats:sc>\n problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time\n O<\/jats:italic>\n (2\n \n n<\/jats:italic>\n <\/jats:sup>\n ), where\n n<\/jats:italic>\n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S\n at<\/jats:sc>\n that run in time\n o<\/jats:italic>\n (2\n \n n<\/jats:italic>\n <\/jats:sup>\n ), no algorithm was able to improve the\n growth rate<\/jats:italic>\n 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The\n strong exponential time hypothesis<\/jats:italic>\n (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every \u03f5 < 1, there is a (large) integer\n k<\/jats:italic>\n such that\n k<\/jats:italic>\n -CNF-S\n at<\/jats:sc>\n cannot be computed in time 2\n \n \u03f5\n n<\/jats:italic>\n <\/jats:sup>\n .\n <\/jats:p>\n \n In this article, we show that, for every \u03f5 < 1, the problems H\n itting<\/jats:sc>\n S\n et<\/jats:sc>\n , S\n et<\/jats:sc>\n S\n plitting<\/jats:sc>\n , and NAE-S\n at<\/jats:sc>\n cannot be computed in time\n O<\/jats:italic>\n (2\n \n \u03f5\n n<\/jats:italic>\n <\/jats:sup>\n ) unless SETH fails. Here\n n<\/jats:italic>\n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S\n et<\/jats:sc>\n C\n over<\/jats:sc>\n and prove that, under this assumption, the fastest known algorithms for S\n teiner<\/jats:sc>\n T\n ree<\/jats:sc>\n , C\n onnected<\/jats:sc>\n V\n ertex<\/jats:sc>\n C\n over<\/jats:sc>\n , S\n et<\/jats:sc>\n P\n artitioning<\/jats:sc>\n , and the pseudo-polynomial time algorithm for S\n ubset<\/jats:sc>\n S\n um<\/jats:sc>\n cannot be significantly improved. Finally, we justify our assumption about the hardness of S\n et<\/jats:sc>\n C\n over<\/jats:sc>\n by showing that the parity of the number of solutions to S\n et<\/jats:sc>\n C\n over<\/jats:sc>\n cannot be computed in time\n O<\/jats:italic>\n (2\n \n \u03f5\n n<\/jats:italic>\n <\/jats:sup>\n ) for any \u03f5 < 1 unless SETH fails.\n <\/jats:p>","DOI":"10.1145\/2925416","type":"journal-article","created":{"date-parts":[[2016,5,25]],"date-time":"2016-05-25T14:07:06Z","timestamp":1464185226000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["On Problems as Hard as CNF-SAT"],"prefix":"10.1145","volume":"12","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Holger","family":"Dell","sequence":"additional","affiliation":[{"name":"Saarland University and Cluster of Excellence (MMCI), Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Technische Universiteie Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[{"name":"University of Electro-Communications, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ramamohan","family":"Paturi","sequence":"additional","affiliation":[{"name":"University of California, San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,5,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_19"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_5_1","unstructured":"Chris Calabro. 2008. A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths. Tech report TR08-110. Electronic Colloquium on Computational Complexity (ECCC). Retrieved from http:\/\/eccc.hpi-web.de\/ eccc-reports\/2008\/TR08-110\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214416"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.05.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635812"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552286"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30559-0_21"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800029.808532"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2009.2326"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133096"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.50"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_59"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17493-3_20"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_2_1_24_1","unstructured":"Rahul Santhanam and Srikanth Srinivasan. 2011. On the Limits of Sparsification. Tech report TR11-131. Electronic Colloquium on Computational Complexity (ECCC). Retrieved from http:\/\/eccc.hpi-web.de\/eccc-reports\/2011\/TR11-131\/."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.012"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79723-4_18"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Johan M. M. van Rooij. 2011. Exact Exponential-Time Algorithms for Domination Problems in Graphs. Ph.D. Dissertation. Utrecht University.","DOI":"10.1007\/s00453-011-9546-x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_50"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000033"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.36"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2925416","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2925416","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2925416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:24:08Z","timestamp":1763457848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2925416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,24]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2925416"],"URL":"https:\/\/doi.org\/10.1145\/2925416","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,24]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}