# Exponential Time Complexity of the Permanent and the Tutte Polynomial

Forskningsoutput: Tidskriftsbidrag › Artikel i vetenskaplig tidskrift

### Standard

**Exponential Time Complexity of the Permanent and the Tutte Polynomial.** / Dell, Holger; Husfeldt, Thore; Marx, Daniel; Taslaman, Nina; Wahlén, Martin.

Forskningsoutput: Tidskriftsbidrag › Artikel i vetenskaplig tidskrift

### Harvard

*ACM Transactions on Algorithms*, vol. 10, nr. 4, s. 21. https://doi.org/10.1145/2635812

### APA

*ACM Transactions on Algorithms*,

*10*(4), 21. https://doi.org/10.1145/2635812

### CBE

### MLA

*ACM Transactions on Algorithms*. 2014, 10(4). 21. https://doi.org/10.1145/2635812

### Vancouver

### Author

### RIS

TY - JOUR

T1 - Exponential Time Complexity of the Permanent and the Tutte Polynomial

AU - Dell, Holger

AU - Husfeldt, Thore

AU - Marx, Daniel

AU - Taslaman, Nina

AU - Wahlén, Martin

PY - 2014

Y1 - 2014

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

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

KW - Theory

KW - Algorithms

KW - Computational complexity

KW - counting problems

KW - Tutte

KW - polynomial

KW - permanent

KW - exponential time hypothesis

U2 - 10.1145/2635812

DO - 10.1145/2635812

M3 - Article

VL - 10

SP - 21

JO - ACM Transactions on Algorithms

T2 - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6333

IS - 4

ER -