Question
Suppose that there exist a deterministic algorithm for solving a #P-complete problem in time $O^*(2^{n / \log(n \log n)})$. What would be the theoretical consequences of such a fact? Would it disprove the ETH (Exponential Time Hypothesis)?
$\begingroup$
$\endgroup$
8
asked Sep 28, 2011 at 21:26
-
3$\begingroup$ The question does not seem to make any sense to me. Are you sure you got the expression right? $\endgroup$– Jukka SuomelaSep 28, 2011 at 22:12
-
1$\begingroup$ I agree. @Walter can you fix this ? $\endgroup$– Suresh VenkatSep 28, 2011 at 22:20
-
9$\begingroup$ (And in general, try to use $a^{b/c}$ instead of $\sqrt[c]{a^b}$; much easier to parse.) $\endgroup$– Jukka SuomelaSep 28, 2011 at 22:24
-
3$\begingroup$ Yeah, could you explain why you picked such an elaborate bound? Is it used in some theorem or as the running time of some algorithm? $\endgroup$– Huck BennettSep 28, 2011 at 22:41
-
2$\begingroup$ @TayfunPay: It is $2^{n / log \ (n log \ n)}$, which is $2^{o(n)}$, which in turn is sub exponential time (and clearly also super polynomial time). Your expression $n^{log \ n}$ is equivalent to $2^{log^2 \ n}$, which is different from my expression (yours is closer to polynomial, mine is closer to exponential). To my naive knowledge, both super polynomial and sub exponential are strictly between polynomial and exponential: the difference is that the former is "more near" to polynomial, while the latter is "more near" to exponential. $\endgroup$– Giorgio CameraniNov 3, 2011 at 17:27
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
8
Solving any old $\# P$-complete problem in $2^{O(n/\log n)}$ time would not necessarily have interesting consequences. In fact there are some $\# P$-complete problems, like counting the number of minimum vertex covers in a planar graph, which can already be done in $2^{O(n^{1/2})}$ time where $n$ is the number of vertices. (Recall that for planar graphs, the number of edges is linear in the number of vertices, so this is truly a subexponential algorithm.)
Added after Walter's recent comment: I should say that there are several $\# P$ problems which are believed to require $2^{\Omega(n)}$ time (such as counting the number of satisfying assignments to a 3-CNF formula), and the time complexities of these problems are closely related: a $2^{o(n)}$-time algorithm for one of them would imply $2^{o(n)}$-time algorithms for all of them. Some recent work in this direction can be found here. I am not 100% certain, but an $2^{O(n/\log n)}$-time algorithm for counting vertex covers in 3-regular graphs may have interesting consequences along these lines.
answered Sep 29, 2011 at 0:24
-
$\begingroup$ Thanks for your answer(s), very helpful to me. In these last week-ends I'm writing a technical document describing the functioning of the algorithm and the reasoning that led to that upper bound. May I notify you as soon as I will finish to write it? I'm almost sure that the upper bound is correct, but I might have overlooked some subtle detail. $\endgroup$ Oct 2, 2011 at 20:27
-
6$\begingroup$ That's fine, Walter. If the algorithm is correct then there should be a great idea which explains why the exponent is $O(n/\log n)$ (and not the expected $O(n)$ that one would get from variants of backtracking search). It may be good to focus on explaining that. $\endgroup$ Oct 6, 2011 at 6:38
-
2$\begingroup$ An $n^{\log n}$ time algorithm for a $\# P$ complete problem would imply that $P^{\# P}$ is contained in $TIME[n^{O(\log n)}]$, mainly because $(n^k)^{\log (n^k)} = n^{k^2 \log n}$. $\endgroup$ Nov 5, 2011 at 15:47
-
2$\begingroup$ If the graph has $O(1)$ nodes, count exactly in $O(1)$ time. Otherwise, find a 1/3-2/3 separator of $k \leq O(\sqrt{n})$ vertices in poly(n) time. For all $2^k$ ways to put the nodes of the separator in-or-out of the vertex cover, remove the nodes of the separator and adjacent edges appropriately. Recurse on the disjoint subgraphs remaining, each having at most $2n/3$ nodes each, obtaining a count. Sum up all counts obtained (they are all distinct vertex covers, thanks to your $2^k$ choices). Runtime recurrence is $T(n) \leq 2^{O(\sqrt{n})}\cdot T(2n/3) + O(poly(n))$ $\endgroup$ Feb 1, 2018 at 2:32
-
2$\begingroup$ Look in the textbook of Fomin and Kratsch; it probably has a reference. $\endgroup$ Feb 4, 2018 at 4:46