3
$\begingroup$

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

$\endgroup$
1
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

This can be done in polynomial time because this is an elementary symmetric polynomial.

Either we can expand a polynomial from the factors as shown in the section "Elementary Symmetric Polynomials" of http://rjlipton.wordpress.com/2009/07/10/arithmetic-complexity-and-symmetry/

Or we can use the Newton-Girard Formulas http://mathworld.wolfram.com/Newton-GirardFormulas.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.