期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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)) .
关键词：counting problems, Exponential Time Hypothesis, permanent, Tutte Polynomial
