Exponential Time Complexity of the Permanent and the Tutte Polynomial

Holger Dell, Thore Husfeldt, Dániel Marx +2

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))…