Exponential Time Complexity of the Permanent and the Tutte Polynomial

Abstract

We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. (b) The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). (c) 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/polylog 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.

References in corpus (4)

• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Inapproximability of the Tutte polynomial
• Exponential Time Complexity of Weighted Counting of Independent Sets
• The Exponential Time Complexity of Computing the Probability That a Graph is Connected

Cited by in corpus (14)

• On Problems as Hard as CNFSAT
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Homomorphisms Are a Good Basis for Counting Small Subgraphs
• How many qubits are needed for quantum computational supremacy?
• Anticoncentration theorems for schemes showing a quantum speedup
• Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
• Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
• Sampling and the complexity of nature
• Fast Witness Counting
• The Long, the Short and the Random
• Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2
• Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
• The Complexity of Computing the Sign of the Tutte Polynomial
• The #ETH is False, #k-SAT is in Sub-Exponential Time