Number of subsets on a set with partial order Given a set $S$ with strict partial order $&lt;$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a&lt;b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-closed?

Are there algorithms that can solve the problem in time polynomial in $|S|$?
See three closely related questions Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits? and Is counting maximal cliques in an incomparability graph #P-complete? and https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset

They are all on antichains rather than downward-closed sets but downward-closed sets correspond one-for-one with the antichains of their maximal elements.

I believe both of the cstheory questions have answers with references that also answer your question: no, the problem is #P-complete.