Exponential Time Complexity of the Permanent and the Tutte Polynomial

Summary, in English

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.

• Författare: Holger Dell; Thore Husfeldt; Daniel Marx; Nina Taslaman; Martin Wahlén
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 21-21
• Publikation/Tidskrift/Serie: ACM Transactions on Algorithms
• Volym: 10
• Issue: 4
• Länkar: http://dx.doi.org/10.1145/2635812
• Dokumenttyp: Artikel i tidskrift
• Förlag: Association for Computing Machinery (ACM)
• Ämne: Computer Science
• Nyckelord: Theory; Algorithms; Computational complexity; counting problems; Tutte; polynomial; permanent; exponential time hypothesis
• Status: Published
• Projekt: Exact algorithms
• Forskningsgrupp: Algorithms
• ISBN/ISSN/Övrigt: ISSN: 1549-6333