[Solved]: Is summing over all possible $k$-combinations NP-hard?

Problem Detail: 

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)$?

Asked By : Tianyang Li

Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23683

 Ask a Question

 Download Related Notes/Documents