Is summing over all possible $k$-combinations NP-hard?

Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute

$$
\sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c \in C} a_c
$$

Naively this requires $O(k\binom{n}{k})$ operations.

This is different from from computing the permanent where there are permutations.

Is this problem known to be NP-hard when $n=2k$ or other conditions such as $n=\Theta(k^2)$?

You can compute the coefficient of $x^k$ in
$$ \prod_{i=1}^n (1+xa_i). $$
Alternatively, you can think of this as a dynamic programming algorithm. Let $b(m,\ell)$ be the sum of $\ell$-combinations of $a_1,\ldots,a_m$. We have
$$ b(m,\ell) = b(m-1,\ell) + a_m b(m-1,\ell-1), $$
where $b(m,-1) = 0$, $b(0,0) = 1$, and $b(0,\ell) = 0$ for $\ell \neq 0$. What you want is $b(n,k)$.

In both cases, there is an optimization that only keeps track of $\ell$-combinations for $\ell \leq k$. In the polynomial representation, it is enough to keep the monomials up to $x^k$. In the dynamic programming approach, we only compute the table up to $b(m,k)$.

StackExchange Computer Science Q#23683, answer score: 5