0
$\begingroup$

Given a set $A \subseteq \{1,2,3,\dots\}$, decide if $\sum_{x \in A} x \neq \sum_{y \in B} y$ for every $B$ that is a combination with repeated usage of $A$.

We define $B$ to be a combination with repeated usage of set $A$ if $B$ is a multiset; every element of $B$ is an element of $A$; and there exists an element in $B$ that occurs with multiplicity 2 or more.

Is this problem coNP-complete?

Observe:

  • $B$ could consist of elements occurring multiple times. For example $a$ could occur two times and $b$ could occur 7 times: $B = \{a,a,b,b,b,b,b,b,b,\dots\}$.

  • $B$ might not have all the elements in $A$, e.g., $A = \{2,4\}$ and $B=\{2,2,2\}$. Both sum up to $6$.

  • When $A = \{2,4\}$, $B=\{2,2,2\}$ sums up to the same as $A$, thus the answer is False in this case.

$\endgroup$
4
  • $\begingroup$ I've encountered this problem by myself, and I'm hoping if someone already has they can tell me what is known about the problem. $\endgroup$
    – The T
    Commented Apr 17 at 18:27
  • $\begingroup$ Wouldn't we need polynomial certificates to show its in coNP? We need to be able to verify the answer with polynomial sized answers. That might be an issue. But maybe we can use something clever. $\endgroup$
    – The T
    Commented Apr 19 at 19:43
  • $\begingroup$ One idea is to use multiplication to represent multiplicities of numbers like when $B$ ={$2,2,2$} we use {$2 * 3$}. This might help us find a polynomial sized certificate for verification. $\endgroup$
    – The T
    Commented Apr 19 at 19:47
  • $\begingroup$ Or when $B$ = {$a,a,b,b,b$} we got 2 $a$'s and three $b$'s the certificate could be represented as $B$ = {$a*2$, $b*3$} $\endgroup$
    – The T
    Commented Apr 19 at 19:54

0

Your Answer

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

Browse other questions tagged or ask your own question.