ITU

Exponential Time Complexity of the Permanent and the Tutte Polynomial

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Standard

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

In: A C M Transactions on Algorithms, Vol. 10, No. 4, 21, 2014, p. 21:1-21:32.

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{0c67d9ddeb0a40bfb565073d93d06193,
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× 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.",
author = "Holger Dell and Thore Husfeldt and D{\'a}niel Marx and Taslaman, {Nina Sofia} and Martin Wahl{\'e}n",
year = "2014",
doi = "10.1145/2635812",
language = "English",
volume = "10",
pages = "21:1--21:32",
journal = "A C M Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery",
number = "4",

}

RIS

TY - JOUR

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

AU - Dell, Holger

AU - Husfeldt, Thore

AU - Marx, Dániel

AU - Taslaman, Nina Sofia

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

U2 - 10.1145/2635812

DO - 10.1145/2635812

M3 - Journal article

VL - 10

SP - 21:1-21:32

JO - A C M Transactions on Algorithms

JF - A C M Transactions on Algorithms

SN - 1549-6325

IS - 4

M1 - 21

ER -

ID: 80233727