uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Computer Science, Humboldt University of Berlin. (Methods for Discrete Structures)
Lunds universitet och IT University of Copenhagen .
Uppsala University, University Administration.
2010 (English)Report (Other academic)
Abstract [en]

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
National Category
Computer Science
Research subject
Computer Science
URN: urn:nbn:se:uu:diva-123592OAI: oai:DiVA.org:uu-123592DiVA: diva2:315004
Available from: 2010-04-28 Created: 2010-04-28

Open Access in DiVA

No full text

Other links

By organisation
University Administration
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 197 hits
ReferencesLink to record
Permanent link

Direct link