Exponential Time Complexity of the Permanent and the Tutte Polynomial (Extended Abstract)

被引：0

作者：

Dell, Holger ^{[1
]}

Husfeldt, Thore ^{[2
,3
]}

Wahlen, Martin ^{[4
,5
]}

机构：

[1] Humboldt Univ, D-1086 Berlin, Germany

[2] IT Univ Copenhagen, S-22100 Lund, Sweden

[3] Lund Univ, S-22100 Lund, Sweden

[4] Lund Univ, S-22100 Lund, Sweden

[5] Uppsala Univ, S-75105 Uppsala, Sweden

来源：

AUTOMATA, LANGUAGES AND PROGRAMMING, PT I | 2010年 / 6198卷

关键词：

NUMBER;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 setting, which makes #ETH robust. Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an n x n matrix with m nonzero entries requires time exp(Omega(m)). Restricted to 01-matrices, the bound is exp(Omega(m/log m)). Computing the Tutte polynomial of a multigraph with n vertices and m edges requires time exp(Omega(n)) at points (x, y) with (x - 1)(y - 1) not equal 1 and y is not an element of {0, +/- 1}. At points (x, 0) with x is not an element of {0, +/- 1} it requires time exp(Omega(n)), and if x = -2, -3, ... , it requires time exp(Omega(m)). For simple graphs, the bound is exp(Omega(m/log(3) m)).

引用

页码：426 / +

页数：2