<p>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.)</p>

<p><strong>Added after Walter's recent comment:</strong> 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 <a href="http://pages.cs.wisc.edu/~holger/papers/dhw10full.pdf">here</a>. 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.</p>

CC BY-SA 3.0
2011-10-02T20:27:48.940Z
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.
Giorgio Camerani
CC BY-SA 3.0
2011-10-06T06:38:48.310Z
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.
Ryan Williams
CC BY-SA 3.0
2011-11-03T22:14:28.753Z
@Ryan How about solving a #P-Complete problem, which is #P-Complete under Cook-like reductions, which runs in n^{log \ n} in the worst case.
Tayfun Pay
CC BY-SA 3.0
2011-11-05T15:47:17.887Z
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}$.
Ryan Williams
CC BY-SA 3.0
2018-01-31T18:15:12.370Z
@RyanWilliams Could you please provide a reference for the $2^{O(n^{1/2})}$ algorithm for counting minimum vertex covers of planar graphs?
delete000
CC BY-SA 3.0
2018-02-01T02:32:21.157Z
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))$
Ryan Williams
CC BY-SA 3.0
2018-02-01T14:50:15.000Z
@RyanWilliams Thanks. Is there a reference for this procedure? Also, I think one can even find an entire separator hierarchy in linear time, see: Goodrich, Michael T. (1995), "Planar separators and parallel polygon triangulation", Journal of Computer and System Sciences, 51 (3): 374–389
delete000
CC BY-SA 3.0
2018-02-04T04:46:07.280Z
Look in the textbook of Fomin and Kratsch; it probably has a reference.
Ryan Williams
CC BY-SA 3.0
2011-09-29T00:24:16.600Z
2011-10-01T18:14:05.587Z
2011-10-01T18:14:05.587Z
Ryan Williams
<blockquote>
  <p><strong>Question</strong></p>
  
  <p>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)?</p>
</blockquote>

CC BY-SA 3.0
2011-09-28T22:12:05.303Z
The question does not seem to make any sense to me. Are you sure you got the expression right?
Jukka Suomela
CC BY-SA 3.0
2011-09-28T22:20:51.493Z
I agree. @Walter can you fix this ?
Suresh Venkat
CC BY-SA 3.0
2011-09-28T22:24:42.047Z
(And in general, try to use $a^{b/c}$ instead of $\sqrt[c]{a^b}$; much easier to parse.)
Jukka Suomela
CC BY-SA 3.0
2011-09-28T22:41:04.063Z
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?
Huck Bennett
CC BY-SA 3.0
2011-09-29T17:41:13.813Z
@All: I made a hasty and wrong reasoning while posting the initial version of the question. Ryan Williams' answer helped me to understand why and where my reasoning was flawed (I had to parse his answer for a while before getting the point). Then I cleaned and rephrased the question. Do you all still believe that the question is meaningless even in this last version?
Giorgio Camerani
CC BY-SA 3.0
2011-09-29T17:43:31.033Z
@HuckBennett: I have an algorithm for counting the number of vertex covers of 3-regular graphs that runs in time at most $\frac{1}{2} m^2 2^{3m/log(nlogn)}$, where $n$ is the number of vertex of the input graph and $m=1.5n$ is the number of edges. I have implemented and tested it, and it works, it always returns the correct vertex cover count. I was able to test it up to $n=60$, $m=90$. I'm **almost** sure of its running time.
Giorgio Camerani
CC BY-SA 3.0
2011-10-28T19:40:22.970Z
@Walter Is it Super Polynomial Time? That is n^log(n) ?
Tayfun Pay
CC BY-SA 3.0
2011-11-03T17:27:35.100Z
@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.
Giorgio Camerani
<cc.complexity-theory><complexity-classes><counting-complexity><time-complexity>
Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem
Giorgio Camerani
# Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

(Asked by: username_0 on 2011-09-28)

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

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, time-complexity

> **Comments:**
> **username_1**: The question does not seem to make any sense to me. Are you sure you got the expression right?  
> **username_2**: I agree. @Walter can you fix this ?  
> **username_1**: (And in general, try to use $a^{b/c}$ instead of $\sqrt[c]{a^b}$; much easier to parse.)  
> **username_3**: 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?  
> **username_0**: @All: I made a hasty and wrong reasoning while posting the initial version of the question. username_5' answer helped me to understand why and where my reasoning was flawed (I had to parse his answer for a while before getting the point). Then I cleaned and rephrased the question. Do you all still believe that the question is meaningless even in this last version?  
> **username_0**: @HuckBennett: I have an algorithm for counting the number of vertex covers of 3-regular graphs that runs in time at most $\frac{1}{2} m^2 2^{3m/log(nlogn)}$, where $n$ is the number of vertex of the input graph and $m=1.5n$ is the number of edges. I have implemented and tested it, and it works, it always returns the correct vertex cover count. I was able to test it up to $n=60$, $m=90$. I'm **almost** sure of its running time.  
> **username_4**: @Walter Is it Super Polynomial Time? That is n^log(n) ?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_5 on 2011-09-29. Score: 18 | Accepted answer

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](http://pages.cs.wisc.edu/~holger/papers/dhw10full.pdf). 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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: 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.  
> **username_4**: @Ryan How about solving a #P-Complete problem, which is #P-Complete under Cook-like reductions, which runs in n^{log \ n} in the worst case.  
> **username_5**: 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}$.  
> **username_6**: @RyanWilliams Could you please provide a reference for the $2^{O(n^{1/2})}$ algorithm for counting minimum vertex covers of planar graphs?  
> **username_5**: 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))$  
> **username_6**: @RyanWilliams Thanks. Is there a reference for this procedure? Also, I think one can even find an entire separator hierarchy in linear time, see: Goodrich, Michael T. (1995), "Planar separators and parallel polygon triangulation", Journal of Computer and System Sciences, 51 (3): 374–389  
> **username_5**: Look in the textbook of Fomin and Kratsch; it probably has a reference.  

---

