Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2635812 | ACM Transactions on Algorithms |
Keywords | DocType | Volume |
n matrix,algorithms,n vertex,m edge,log3 m,exponential time complexity,exponential time hypothesis,permanent,3-cnf formula,computational complexity,m nonzero entry,p-hard problem,counting problems,theory,lower bound,time exp,tutte polynomial,polynomial,computer science | Journal | 10 |
Issue | ISSN | ISBN |
4 | 1549-6325 | 3-642-14164-1 |
Citations | PageRank | References |
18 | 1.15 | 33 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Holger Dell | 1 | 220 | 16.74 |
| Thore Husfeldt | 2 | 733 | 40.87 |
| Dániel Marx | 3 | 1952 | 113.07 |
| Nina Taslaman | 4 | 38 | 2.61 |
| Martin Wahlen | 5 | 39 | 4.43 |