5
$\begingroup$

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)?

$\endgroup$
  • 3
    $\begingroup$ The question does not seem to make any sense to me. Are you sure you got the expression right? $\endgroup$ – Jukka Suomela Sep 28 '11 at 22:12
  • 1
    $\begingroup$ I agree. @Walter can you fix this ? $\endgroup$ – Suresh Venkat Sep 28 '11 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 Suomela Sep 28 '11 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 Bennett Sep 28 '11 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 Camerani Nov 3 '11 at 17:27
17
$\begingroup$

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.

$\endgroup$
  • $\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$ – Giorgio Camerani Oct 2 '11 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$ – Ryan Williams Oct 6 '11 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$ – Ryan Williams Nov 5 '11 at 15:47
  • 1
    $\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$ – Ryan Williams Feb 1 '18 at 2:32
  • 1
    $\begingroup$ Look in the textbook of Fomin and Kratsch; it probably has a reference. $\endgroup$ – Ryan Williams Feb 4 '18 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.