Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an
n×
n matrix with
m nonzero entries requires time
exp(W(m))\exp(\Omega(m)). Restricted to 01-matrices, the bound is
exp(W(m/logm))\exp(\Omega(m/\log m)). Computing the Tutte polynomial of a multigraph with
n vertices and
m edges requires time
exp(W(n))\exp(\Omega(n)) at points (
x,
y) with (
x − 1)(
y − 1) ≠ 1 and
y ∉ {0,±1}. At points (
x,0) with
x \not Î {0,±1}x \not \in \{0,\pm 1\} it requires time
exp(W(n))\exp(\Omega(n)), and if
x = − 2, − 3,..., it requires time
exp(W(m))\exp(\Omega(m)). For simple graphs, the bound is
exp(W(m/log3 m))\exp(\Omega(m/\log^3 m)).