# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Exponential Time Complexity of the Permanent and the Tutte Polynomial

; ; ; and (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)
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)
2016-04-01 10:37:22
date last changed
2021-10-06 02:50:17
```@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},
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},
}

```