Exponential Time Complexity of the Permanent and the Tutte Polynomial
2010 (English)Report (Other academic)
The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of n-variable 3-CNF formulas requires time exp((n)). We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time exp((n)). We transfer the sparsification lemma for d-CNF formulas to the counting setting, which makes #ETH robust.
Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an nn matrix with m nonzero entries requires time exp((m)). Restricted to 01-matrices, the bound is exp((mlogm)) . Computing the Tutte polynomial of a multigraph with n vertices and m edges requires time exp((n)) at points (xy) with (x−1)(y−1)=1 and y01 . At points (x0) with x01 it requires time exp((n)), and if x=−2−3 , it requires time exp((m)). For simple graphs, the bound is exp((mlog3m)) .
Place, publisher, year, edition, pages
2010. , 25 p.
, Electronic Colloquium on Computational Complexity, ISSN ISSN 1433-8092 ; TR10-078
Research subject Computer Science
IdentifiersURN: urn:nbn:se:uu:diva-123592OAI: oai:DiVA.org:uu-123592DiVA: diva2:315004