2
$\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$

2 Answers 2

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$
4
  • $\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$ Commented Jun 12, 2018 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.
    Commented Jun 12, 2018 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$ Commented Jun 14, 2018 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.
    Commented Jun 14, 2018 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$
2
  • $\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$ Commented Jun 12, 2018 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$ Commented Jun 12, 2018 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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