Exponential Time Complexity of the Permanent and the Tutte Polynomial
Research output: Contribution to journal › Article
Abstract
We show conditional lower bounds for wellstudied #Phard problems: The number of satisfying assignments of a 2CNF 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 nvertex 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 nvertex 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 nvariable 3CNF 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 dCNF formulas to the counting setting.
Details
Authors  

Organisations  
External organisations 

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Pages (fromto)  21 
Journal  ACM Transactions on Algorithms 
Volume  10 
Issue number  4 
Publication status  Published  2014 
Publication category  Research 
Peerreviewed  Yes 