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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
Electronic Colloquium on Computational Complexity, ISSN ISSN 1433-8092 ; TR10-078
National Category
Computer Science
Research subject
Computer Science
Identifiers
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

http://eccc.hpi-web.de/report/2010/078/
By organisation
University Administration
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 501 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf