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