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$
  • $\begingroup$ Are the values $S_i$ in any way bounded? $\endgroup$ – Pedro Jul 19 '13 at 10:01
  • $\begingroup$ Yes, they are bounded. $\endgroup$ – s_xavier Jul 19 '13 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 '13 at 17:24
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It looks like the number of computations is exponential in $k$. $\endgroup$ – s_xavier Jul 19 '13 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$ – Hendrik Jan Jul 19 '13 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 '13 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 '13 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 '13 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$
  • $\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 '13 at 8:01

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.