{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T03:11:05Z","timestamp":1784257865583,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["PARAMTIGHT (280152)"],"award-info":[{"award-number":["PARAMTIGHT (280152)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1017597"],"award-info":[{"award-number":["1017597"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>We show conditional lower bounds for well-studied #P-hard problems:<\/jats:p>\n          <jats:p>\n            The number of satisfying assignments of a 2-CNF formula with\n            <jats:italic>n<\/jats:italic>\n            variables cannot be computed in time exp(\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )), and the same is true for computing the number of all independent sets in an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph.\n          <\/jats:p>\n          <jats:p>\n            The permanent of an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix with entries 0 and 1 cannot be computed in time exp(\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )).\n          <\/jats:p>\n          <jats:p>\n            The Tutte polynomial of an\n            <jats:italic>n<\/jats:italic>\n            -vertex multigraph cannot be computed in time exp(\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )) at most evaluation points (\n            <jats:italic>x<\/jats:italic>\n            ,\n            <jats:italic>y<\/jats:italic>\n            ) in the case of multigraphs, and it cannot be computed in time exp(\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/poly log\n            <jats:italic>n<\/jats:italic>\n            )) in the case of simple graphs.\n          <\/jats:p>\n          <jats:p>\n            Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of\n            <jats:italic>n<\/jats:italic>\n            -variable 3-CNF formulas cannot be decided in time exp(\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp(\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for\n            <jats:italic>d<\/jats:italic>\n            -CNF formulas to the counting setting.\n          <\/jats:p>","DOI":"10.1145\/2635812","type":"journal-article","created":{"date-parts":[[2014,8,21]],"date-time":"2014-08-21T12:19:12Z","timestamp":1408623552000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Exponential Time Complexity of the Permanent and the Tutte Polynomial"],"prefix":"10.1145","volume":"10","author":[{"given":"Holger","family":"Dell","sequence":"first","affiliation":[{"name":"LIAFA, Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Denmark and Lund University, Sweden"}],"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":"Nina","family":"Taslaman","sequence":"additional","affiliation":[{"name":"Malm\u00f6 University, Malm\u00f6, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Wahl\u00e9n","sequence":"additional","affiliation":[{"name":"Lund University, Sweden and Uppsala University, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,8,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 25th International Congress of Mathematicians (ICM\u201906)","volume":"3","author":"Agrawal Manindra","year":"2006","unstructured":"Manindra Agrawal . 2006 . Determinant versus permanent . In Proceedings of the 25th International Congress of Mathematicians (ICM\u201906) , Vol. 3 . 985--997. Manindra Agrawal. 2006. Determinant versus permanent. In Proceedings of the 25th International Congress of Mathematicians (ICM\u201906), Vol. 3. 985--997."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9149-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.40"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394633"},{"key":"e_1_2_1_6_1","volume-title":"Matroid theory and its applications. Centro Internazionale Matematico Estivo","author":"Brylawski Thomas","year":"1982","unstructured":"Thomas Brylawski . 1982. The Tutte polynomial , Matroid theory and its applications. Centro Internazionale Matematico Estivo ( 1982 ), 125--275. Thomas Brylawski. 1982. The Tutte polynomial, Matroid theory and its applications. Centro Internazionale Matematico Estivo (1982), 125--275."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP\u201901)","author":"Cai Liming","unstructured":"Liming Cai and David W. Juedes . 2001. Subexponential parameterized algorithms collapse the W-Hierarchy . In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP\u201901) . 273--284. Liming Cai and David W. Juedes. 2001. Subexponential parameterized algorithms collapse the W-Hierarchy. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP\u201901). 273--284."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214416"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_10_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910)","author":"Dell Holger","unstructured":"Holger Dell , Thore Husfeldt , and Martin Wahl\u00e9n . 2010. Exponential time complexity of the permanent and the Tutte polynomial . In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910) . Lecture Notes in Computer Science , vol. 6198 . Springer , 426--437. DOI: http:\/\/dx.doi.org\/10.1007\/978-3-642-14165-2_37 10.1007\/978-3-642-14165-2_37 Holger Dell, Thore Husfeldt, and Martin Wahl\u00e9n. 2010. Exponential time complexity of the permanent and the Tutte polynomial. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910). Lecture Notes in Computer Science, vol. 6198. Springer, 426--437. DOI: http:\/\/dx.doi.org\/10.1007\/978-3-642-14165-2_37"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_1_13_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645208"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.04.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600767X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.04.003"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17493-3_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17493-3_19"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335316"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.013"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322341"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.06.017"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0607036"},{"key":"e_1_2_1_32_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","unstructured":"Christos H. Papadimitriou . 1994. Computational Complexity . Addison-Wesley . Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/646338.688589"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303006023"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371127"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635812","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2635812","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:03:44Z","timestamp":1750273424000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635812"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2635812"],"URL":"https:\/\/doi.org\/10.1145\/2635812","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}