Exponential Time Complexity of the Permanent and the Tutte Polynomial
(2014) In ACM Transactions on Algorithms 10(4). p.2121 Abstract
 We show conditional lower bounds for wellstudied #Phard problems: The number of satisfying assignments of a 2CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an nvertex graph. The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). The Tutte polynomial of an nvertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x, y) in the case of multigraphs, and it cannot be computed in time exp(o(n/poly log n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of nvariable 3CNF formulas... (More)
 We show conditional lower bounds for wellstudied #Phard problems: The number of satisfying assignments of a 2CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an nvertex graph. The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). The Tutte polynomial of an nvertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x, y) in the case of multigraphs, and it cannot be computed in time exp(o(n/poly log n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of nvariable 3CNF formulas cannot be decided in time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for dCNF formulas to the counting setting. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/4882025
 author
 Dell, Holger; Husfeldt, Thore ^{LU} ; Marx, Daniel; Taslaman, Nina and Wahlén, Martin ^{LU}
 organization
 publishing date
 2014
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Theory, Algorithms, Computational complexity, counting problems, Tutte, polynomial, permanent, exponential time hypothesis
 in
 ACM Transactions on Algorithms
 volume
 10
 issue
 4
 pages
 21  21
 publisher
 ACM
 external identifiers

 wos:000343962200005
 scopus:84906849708
 ISSN
 15496333
 DOI
 10.1145/2635812
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 150f1b14f2484cd99cc90151838b7050 (old id 4882025)
 date added to LUP
 20141222 11:24:28
 date last changed
 20190319 01:18:43
@article{150f1b14f2484cd99cc90151838b7050, abstract = {We show conditional lower bounds for wellstudied #Phard problems: The number of satisfying assignments of a 2CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an nvertex graph. The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). The Tutte polynomial of an nvertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x, y) in the case of multigraphs, and it cannot be computed in time exp(o(n/poly log n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of nvariable 3CNF formulas cannot be decided in time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for dCNF formulas to the counting setting.}, author = {Dell, Holger and Husfeldt, Thore and Marx, Daniel and Taslaman, Nina and Wahlén, Martin}, issn = {15496333}, keyword = {Theory,Algorithms,Computational complexity,counting problems,Tutte,polynomial,permanent,exponential time hypothesis}, language = {eng}, number = {4}, pages = {2121}, publisher = {ACM}, series = {ACM Transactions on Algorithms}, title = {Exponential Time Complexity of the Permanent and the Tutte Polynomial}, url = {http://dx.doi.org/10.1145/2635812}, volume = {10}, year = {2014}, }