Sökning: onr:"swepub:oai:lup.lub.lu.se:150f1b14-f248-4cd9-9cc9-0151838b7050" >
Exponential Time Co...
Exponential Time Complexity of the Permanent and the Tutte Polynomial
-
- Dell, Holger (författare)
- LIAFA, Université Paris Diderot, Paris, France
-
- Husfeldt, Thore (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH,IT University of Copenhagen, Denmark; Lund University, Sweden
-
- Marx, Daniel (författare)
- Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary
-
visa fler...
-
- Taslaman, Nina (författare)
- Malmö högskola,Fakulteten för teknik och samhälle (TS)
-
- Wahlén, Martin (författare)
- Uppsala universitet,Uppsala University,Områdeskanslier,Lund University, Sweden; Uppsala University, Sweden
-
visa färre...
-
(creator_code:org_t)
- 2014-08-13
- 2014
- Engelska.
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 10:4, s. 21-21
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
http://eprints.sztak...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- We show conditional lower bounds for well-studied #P-hard problems: -The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. -The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). -The Tutte polynomial of an n-vertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x, y) in the case of multigraphs, and it cannot be computed in time exp(o(n/poly log n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n-variable 3-CNF formulas cannot be decided in time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d-CNF formulas to the counting setting.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Theory
- Algorithms
- Computational complexity
- counting problems
- Tutte
- polynomial
- permanent
- exponential time hypothesis
- Theory
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas