We 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.

We extended the results for the Tutte polynomial, we added tighter results for #2-Sat and the permanent, and we integrated the results of Husfeldt and Taslaman [IPEC 2010] into this version.

The 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))$.