## 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.

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.

Original language | English |
---|---|

Article number | 21 |

Journal | A C M Transactions on Algorithms |

Volume | 10 |

Issue number | 4 |

Pages (from-to) | 21:1-21:32 |

Number of pages | 32 |

ISSN | 1549-6325 |

DOIs | |

Publication status | Published - 2014 |

## Keywords

- #P-hard problems
- Conditional lower bounds
- Exponential Time Hypothesis (ETH)
- #ETH (counting version of ETH)
- Sparsification lemma