# Computational complexity of Bell numbers

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.

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

• 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. – sdgaw erzswer Jun 12 '18 at 5:26
• @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. – D.W. Jun 12 '18 at 15:47
• 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}$? – sdgaw erzswer Jun 14 '18 at 6:13
• $\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}$. – D.W. Jun 14 '18 at 6:21

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.

• Thanks, this is also very interesting. Could you at least give me a direction as to where is the k=[n/lg n] written? – sdgaw erzswer Jun 12 '18 at 12:33
• @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. – András Salamon Jun 12 '18 at 12:54