uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Show others and affiliations
2014 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 10, no 4, 21- p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2014. Vol. 10, no 4, 21- p.
Keyword [en]
Theory, Algorithms, Computational complexity, counting problems, Tutte polynomial, permanent, exponential time hypothesis
National Category
Computer Science
URN: urn:nbn:se:uu:diva-238091DOI: 10.1145/2635812ISI: 000343962200005OAI: oai:DiVA.org:uu-238091DiVA: diva2:773861
Available from: 2014-12-19 Created: 2014-12-09 Last updated: 2014-12-19Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Wahlén, Martin
By organisation
Faculty Offices
In the same journal
ACM Transactions on Algorithms
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 138 hits
ReferencesLink to record
Permanent link

Direct link