<p>Recently, two independent groups of researchers exactly calculated the <span class="math-container">$9$</span>th Dedekind Number (see e.g. <a href="https://www.quantamagazine.org/ninth-dedekind-number-found-by-two-independent-groups-20230801/" rel="nofollow noreferrer">Quanta</a>). The <span class="math-container">$n$</span>th Dedekind Number counts the number of antichains consisting of subsets of <span class="math-container">$\{1,2,\ldots,n\}$</span>, that is, the number of subsets <span class="math-container">$\mathcal T$</span> of the power set of <span class="math-container">$\{1,2,\ldots,n\}$</span> such that for every distinct pair <span class="math-container">$A, B \in \mathcal T$</span>, neither <span class="math-container">$A \subseteq B$</span> nor <span class="math-container">$B \subseteq A$</span>. Since calculating the <span class="math-container">$9$</span>th element was covered by Quanta, it's seemingly quite difficult to calculate this sequence.</p>
<p>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?</p>
<p>On one hand, the problem is a special case of counting the number of anti-chains in some partial order, which is <a href="https://epubs.siam.org/doi/10.1137/0212053" rel="nofollow noreferrer">known to be <span class="math-container">$\#P$</span>-hard</a>. Moreover, the partial order is exponential-sized in <span class="math-container">$n$</span>. (On the other hand, the partial order is very regular and easy to describe---the power set of the <span class="math-container">$n$</span>-element set.)</p>
<p>For this reason (and because the output of the problem takes exponentially-many bits to write down---the sequence is <a href="https://en.wikipedia.org/wiki/Dedekind_number" rel="nofollow noreferrer">known to</a> grow like <span class="math-container">$2^{2^{\Theta(n)}}$</span>) the complexity class <span class="math-container">$\#P$</span> does not seem like ``enough'' to capture this problem (perhaps additionally explaining why computing even the <span class="math-container">$9$</span>th element is so hard).
Is there a studied class of counting problems far above <span class="math-container">$\#P$</span>, i.e. something like <span class="math-container">$\#EXP$</span>, which one might define to be the number of accepting paths of a <span class="math-container">$NEXP$</span> machine?
More generally, are there hardness results for computing concrete combinatorial sequences like this?</p>

CC BY-SA 4.0
2023-10-18T06:06:19.813Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-10-18T15:44:12.627Z
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...
Clay Thomas
CC BY-SA 4.0
2023-10-19T18:07:24.510Z
@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
Command Master
<co.combinatorics><complexity-classes><counting-complexity>
Computational complexity of finding the $n$th Dedekind Number
Clay Thomas
# Computational complexity of finding the $n$th Dedekind Number

(Asked by: username_0 on 2023-10-17)

Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. [Quanta](https://www.quantamagazine.org/ninth-dedekind-number-found-by-two-independent-groups-20230801/)). 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](https://epubs.siam.org/doi/10.1137/0212053). 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](https://en.wikipedia.org/wiki/Dedekind_number) 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?

**Tags:** co.combinatorics, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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...  
> **username_2**: @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  

---

## 0 answers

