1
$\begingroup$

I've been recently dealing with a problem which, when worst case is considered, results in exploration of $B_{n}$ options, where $B_{n}$ is th $n^{th}$ Bell number. I am trying to rigorously prove, that dealing with $B_{n}$ possible solutions results in exponential (or worse?) computational complexity (in terms of $n$). If possible, I would also like to prove this in the context of NP-hardness.

As I am new to this, any hints would be greatly appreciated.

So to summarize, given an algorithm, prove that it will take exponential (or worse) time in terms of $n$, when $n$ corresponds to $B_{n}$.

Thank you very much.

$\endgroup$
3
$\begingroup$

Yes, the $n$th Bell number is exponential in $n$. Wikipedia lists the following relation:

$$B_{n+1} = \sum_{k=0}^n {n \choose k} B_k.$$

It follows that

$$B_{n+1} \ge B_n + n B_{n-1} \ge n B_{n-1},$$

so

$$B_{n+1} \ge n(n-2)(n-4)\cdots \ge (n/2)^{n/4},$$

which is exponential in $n$.


This fact has little or nothing to do with NP-hardness; it is just unconditionally true, regardless of whether P = NP or not.

If you have a problem for which every algorithm takes $\Omega(B_n)$ time, then the problem is not in P; it requires exponential time. It might or might not be in NP.

If you have a problem where the obvious algorithm takes $\Theta(B_n)$ time, that proves nothing (maybe there is some other algorithm you haven't thought of yet that is faster).

$\endgroup$
  • $\begingroup$ One sub-question, now that I think of it. How did you obtain the middle part of the third line? Where does the n(n-2)... connection come from? Thank you. $\endgroup$ – sdgaw erzswer Jun 12 '18 at 5:26
  • $\begingroup$ @sdgawerzswer, $B_{n+1} \ge n B_{n-1}$, and $B_{n-1} \ge (n-2) B_{n-3}$, and so on. Combining all of these gives the inequality shown. $\endgroup$ – D.W. Jun 12 '18 at 15:47
  • $\begingroup$ Sorry to interrupt again, yet I have one final question. How does one know n(n-2)(n-4).. amounts to $\leq$$ (n/2)^{n/4}$? Isn't this more like $(n something)^{n/2}$? $\endgroup$ – sdgaw erzswer Jun 14 '18 at 6:13
  • $\begingroup$ $\ge (n/2)^{n/4}$, not $\le$. Note that $n(n-2)(n-4)\cdots 2 \ge n(n-2)(n-4)\cdots (n/2)$; and each term of the latter product is at least $n/2$; and there are $n/4$ terms in the product; so it must be at least $(n/2)^{n/4}$. $\endgroup$ – D.W. Jun 14 '18 at 6:21
2
$\begingroup$

There is an easy lower bound for $B_n$.

Let $[n] = \{1,2,\dots,n\}$. Pick some $k$-element set $S \subseteq [n]$. Form the set $X = \{\{x\} \mid x \in S\}$ of singletons from $S$. There are $k^{n-k}$ ways to add the remaining $n-k$ elements of $[n]$ to the sets in $X$, and these form distinct partitions of $[n]$. (Not all partitions of $[n]$ can be obtained in this way, so this is only a lower bound.)

So $B_n > k^{n-k}$. When $n$ is even, a nice value for $k$ is $k = n/2$, and then $B_n > (n/2)^{n/2}$. The best bound is when $k = \lceil n/\lg n\rceil$ but it is a bit messier to write out.

$\endgroup$
  • $\begingroup$ Thanks, this is also very interesting. Could you at least give me a direction as to where is the k=[n/lg n] written? $\endgroup$ – sdgaw erzswer Jun 12 '18 at 12:33
  • $\begingroup$ @sdgawerzswer, I don't understand your question: are you asking for a pointer to a source? This hasn't been published as far as I know but the argument is a standard one in combinatorics, and there is a detailed proof in my ECCC report TR12-183. $\endgroup$ – András Salamon Jun 12 '18 at 12:54

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.