# Exponential Time Complexity of the Permanent and the Tutte Polynomial

Forskningsoutput: Tidskriftsbidrag › Artikel i vetenskaplig tidskrift

### Bibtex

@article{150f1b14f2484cd99cc90151838b7050,

title = "Exponential Time Complexity of the Permanent and the Tutte Polynomial",

abstract = "We show conditional lower bounds for well-studied #P-hard problems: -The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. -The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). -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/poly log 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.",

keywords = "Theory, Algorithms, Computational complexity, counting problems, Tutte, polynomial, permanent, exponential time hypothesis",

author = "Holger Dell and Thore Husfeldt and Daniel Marx and Nina Taslaman and Martin Wahl{\'e}n",

year = "2014",

doi = "10.1145/2635812",

language = "English",

volume = "10",

pages = "21",

journal = "ACM Transactions on Algorithms",

issn = "1549-6333",

publisher = "ACM",

number = "4",

}