3
$\begingroup$

Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. Quanta). The $n$th Dedekind Number counts the number of antichains consisting of subsets of $\{1,2,\ldots,n\}$, that is, the number of subsets $\mathcal T$ of the power set of $\{1,2,\ldots,n\}$ such that for every distinct pair $A, B \in \mathcal T$, neither $A \subseteq B$ nor $B \subseteq A$. Since calculating the $9$th element was covered by Quanta, it's seemingly quite difficult to calculate this sequence.

This made me curious: What, if anything, is known about the computational complexity of this problem? What even is a suitable complexity class for the problem to lie in?

On one hand, the problem is a special case of counting the number of anti-chains in some partial order, which is known to be $\#P$-hard. Moreover, the partial order is exponential-sized in $n$. (On the other hand, the partial order is very regular and easy to describe---the power set of the $n$-element set.)

For this reason (and because the output of the problem takes exponentially-many bits to write down---the sequence is known to grow like $2^{2^{\Theta(n)}}$) the complexity class $\#P$ does not seem like ``enough'' to capture this problem (perhaps additionally explaining why computing even the $9$th element is so hard). Is there a studied class of counting problems far above $\#P$, i.e. something like $\#EXP$, which one might define to be the number of accepting paths of a $NEXP$ machine? More generally, are there hardness results for computing concrete combinatorial sequences like this?

$\endgroup$
3
  • 3
    $\begingroup$ The problem is not going to be hard for any reasonable class like #EXP, because the input is in unary, thus there is only one output value for each input length. $\endgroup$ Oct 18, 2023 at 6:06
  • $\begingroup$ Fair. Maybe this is a dumb question, but what about reasonable "tweaks" of the problem? E.g. having the input in binary, and considering the decision problem of finding the last bit of the output? I'm now curious whether any complexity-type results are known for computing any similar (mathematically canonical) sequences... $\endgroup$ Oct 18, 2023 at 15:44
  • 1
    $\begingroup$ @ClayThomas I'm not aware of any such mathematical problems with hardness results, even for well known problems like factoring, mainly because most interesting functions on numbers are too... simple... to encode stuff like SAT $\endgroup$ Oct 19, 2023 at 18:07

0

Your Answer

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