0
$\begingroup$

I'm trying to proove $NP$-membership for a problem from the following certificate. I have $n$ sets of integers : $$(S_i)_{i \in \{1,\dots,n\}}$$ Each set has a number $m_i$ of integers. I make "combination" from those sets by taking at most one element in each set. A "combination" has between $0$ and $n$ elements (assuming sets are not empty). A "combination" has a value : the sum of its elements. I have to compute the sum of every possible "combination" values, and look if it is greater than a given value. An analytical formula would be nice, but I'm not sure it exists. Otherwise, do you think this sum is easily computable ?

$\endgroup$
3
  • $\begingroup$ Are the values $S_i$ in any way bounded? $\endgroup$
    – Pedro
    Jul 19, 2013 at 10:01
  • $\begingroup$ Yes, they are bounded. $\endgroup$
    – s_xavier
    Jul 19, 2013 at 14:26
  • $\begingroup$ What have you tried so far? Where did you come across this problem? We generally expect people to provide some context and show what research they've done so far and what they've tried so far and where they've gotten stuck. $\endgroup$
    – D.W.
    Jul 19, 2013 at 17:24

2 Answers 2

1
$\begingroup$

$C_0=\{0\}$, $C_{k} = C_{k-1} \cup \{ x+y \mid x\in C_{k-1}, y\in S_k \}$.

$\endgroup$
6
  • $\begingroup$ It looks like the number of computations is exponential in $k$. $\endgroup$
    – s_xavier
    Jul 19, 2013 at 14:26
  • 1
    $\begingroup$ Yes. If the sets are $S_1=\{1\}$, $S_2=\{2\}$, ..., $S_n = \{2^{n-1}\}$, then the "combinations" form $C_n = \{0,1,\dots, 2^n-1\}$. $\endgroup$ Jul 19, 2013 at 15:05
  • $\begingroup$ I'm searching for a polynomial time algorithm, or a proof of non polynomial time computability. $\endgroup$
    – s_xavier
    Jul 19, 2013 at 15:27
  • $\begingroup$ @s_xavier, please edit your question to clarify what you are looking for. Right now, that's not clear from your question. P.S. Polynomial in what? Hendrik's solution is polynomial in the bound on the elements of your sets, but not polynomial in the number of bits to describe the problem instance. Is that good enough? $\endgroup$
    – D.W.
    Jul 19, 2013 at 17:24
  • $\begingroup$ Polynomial in the number of bits required to describe the problem instance is what I need. Thanks for responses and help. Note that a set $S_i$ may have any number of elements but may not be empty. This problem occurs while verifying a certificate for another decision problem of which I want to prove $NP$ membership. $\endgroup$
    – s_xavier
    Jul 19, 2013 at 18:35
0
$\begingroup$

Let $x_{ij}$ be the $j^{th}$ element of $S_i$ and let $S$ denote the sum of all combinations. We consider $S$ as $$S = \Sigma \;x_{ij} \cdot w_{ij}$$ where $w_{ij}$ is the number of combinations that contain $x_{ij}$.

Consider an arbitrary element $x$ of $S_1$. There are $(m_2+1) \cdot (m_3+1) \cdots (m_n+1)$ possible combinations that contain $x$ (i.e.: pick any of the $m_2$ elements of $S_2$ or none, pick any of the $m_3$ elements of $S_3$ or none, etc...). So, in general, $w_{ij} = \left(\Pi_{k=1}^n(m_k+1) \right)/(m_i+1)$.

Note: This is assuming that the question is asking for the sum of the values of all combinations. If the real question is the sum of the values of all distinct combinations, this will not work.

$\endgroup$
1
  • $\begingroup$ It is about the sum of the values of all combinations. In the preceding answer the set notation is not correct. $\endgroup$
    – s_xavier
    Jul 20, 2013 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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