Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TUTTE POLYNOMIAL:
Reports tagged with Tutte Polynomial:
TR10-078 | 27th April 2010
Holger Dell, Thore Husfeldt, Martin Wahlén

Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>




ISSN 1433-8092 | Imprint