ECCC-Report TR10-078https://eccc.weizmann.ac.il/report/2010/078Comments and Revisions published for TR10-078en-usFri, 08 Jun 2012 17:51:59 +0300
Revision 1
| Exponential Time Complexity of the Permanent and the Tutte Polynomial |
Holger Dell,
Thore Husfeldt,
Dániel Marx,
Nina Taslaman,
Martin Wahlén
https://eccc.weizmann.ac.il/report/2010/078#revision1We show conditional lower bounds for well-studied #P-hard problems:
(a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph.
(b) The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)).
(c) The Tutte polynomial of an n-vertex 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/polylog 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 n-variable 3-CNF 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 d-CNF formulas to the counting setting.Fri, 08 Jun 2012 17:51:59 +0300https://eccc.weizmann.ac.il/report/2010/078#revision1
Paper TR10-078
| Exponential Time Complexity of the Permanent and the Tutte Polynomial |
Holger Dell,
Thore Husfeldt,
Martin Wahlén
https://eccc.weizmann.ac.il/report/2010/078The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting setting, which makes #ETH robust.
Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an $n\times n$ matrix with $m$ nonzero entries requires time $\exp(\Omega(m))$. Restricted to 01-matrices, the bound is $\exp(\Omega(m/\log m))$. Computing the Tutte polynomial of a multigraph with $n$ vertices and $m$ edges requires time $\exp(\Omega(n))$ at points $(x,y)$ with $(x-1)(y-1)\neq 1$ and $y\notin\{0,\pm 1\}$. At points $(x,0)$ with $x \not \in \{0,\pm 1\}$ it requires time $\exp(\Omega(n))$, and if $x=-2,-3,\ldots$, it requires time $\exp(\Omega(m))$. For simple graphs, the bound is $\exp(\Omega(m/\log^3 m))$.Tue, 27 Apr 2010 23:50:50 +0300https://eccc.weizmann.ac.il/report/2010/078