Exponential Time Complexity of the Permanent and the Tutte Polynomial (Extended Abstract)

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 x 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) not equal 1 and y is not an element of {0, +/- 1}. At points (x, 0) with x is not an element of {0, +/- 1} it requires time exp(Omega(n)), and if x = -2, -3, ... , it requires time exp(Omega(m)). For simple graphs, the bound is exp(Omega(m/log(3) m)).