Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Exponential Time Complexity of the Permanent and the Tutte Polynomial

Dell, Holger ; Husfeldt, Thore LU ; Marx, Daniel ; Taslaman, Nina and Wahlén, Martin LU (2014) In ACM Transactions on Algorithms 10(4). p.21-21
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Theory, Algorithms, Computational complexity, counting problems, Tutte, polynomial, permanent, exponential time hypothesis
in
ACM Transactions on Algorithms
volume
10
issue
4
pages
21 - 21
publisher
Association for Computing Machinery (ACM)
external identifiers
  • wos:000343962200005
  • scopus:84906849708
ISSN
1549-6333
DOI
10.1145/2635812
project
Exact algorithms
language
English
LU publication?
yes
id
150f1b14-f248-4cd9-9cc9-0151838b7050 (old id 4882025)
date added to LUP
2016-04-01 10:37:22
date last changed
2022-04-20 03:52:08
@article{150f1b14-f248-4cd9-9cc9-0151838b7050,
  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.}},
  author       = {{Dell, Holger and Husfeldt, Thore and Marx, Daniel and Taslaman, Nina and Wahlén, Martin}},
  issn         = {{1549-6333}},
  keywords     = {{Theory; Algorithms; Computational complexity; counting problems; Tutte; polynomial; permanent; exponential time hypothesis}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{21--21}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  series       = {{ACM Transactions on Algorithms}},
  title        = {{Exponential Time Complexity of the Permanent and the Tutte Polynomial}},
  url          = {{http://dx.doi.org/10.1145/2635812}},
  doi          = {{10.1145/2635812}},
  volume       = {{10}},
  year         = {{2014}},
}