0
$\begingroup$

An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset.

However, I want to know, is it possible to create a new instance $T$, the same size as the original set $S$, that any subset in $S$ that evaluates to $W$, the corresponding subset in $T$ (the numbers taken from the same positions) evaluates to $0$? All other subsets in $T$ should evaluate to $1$.

Bonus: Give a list of other NP-complete problems (other than 3SAT, where you evaluate a formula that either outputs $0$ or $1$ depending on the set of binary variables being passed into it), where evaluating an analogous instance outputs $0$ if it satisfies some objective related to the problem and $1$ otherwise.

$\endgroup$
6
  • $\begingroup$ I'm confused by this question. I don't know what you mean by "find the sum of a selection of numbers in the set"; which numbers? Is it possible to modify an instance? Sure, you can do whatever you want. What exactly are you asking? $\endgroup$
    – D.W.
    Sep 14 '20 at 6:21
  • $\begingroup$ @D.W. 1. For example, take a set $\{3,4,5,6\}$. Evaluating a set could mean finding the sum of a particular selection of numbers in the set, like $\{3,4\}$ or just $\{3\}$. 2. I'm asking that for any particular set (the $n$th set could be defined as you'll like, the most common is to take a number $n$, convert it to binary, and sum the numbers whose positions correspond with $1$s), can you adjust the instance that for a weight $W$, the output of a set would be $0$ iff the sum of the corresponding set equals $W$, and $1$ otherwise. $\endgroup$
    – DUO Labs
    Sep 14 '20 at 17:38
  • $\begingroup$ "Evaluating" is pretty unclear language. Are you asking: given a set $S$ and a target $W$, find a new set $T$ so that there exists a subset of $S$ that sums to $W$ iff there exists a subset of $T$ that sums to 0? $\endgroup$
    – D.W.
    Sep 14 '20 at 17:39
  • $\begingroup$ @D.W. Yes, and the second part is that all other subsets of $S$ that don't add to $W$, the corresponding set in $T$ should sum to $1$. $\endgroup$
    – DUO Labs
    Sep 14 '20 at 17:42
  • $\begingroup$ What do you mean by "corresponding"? Are you requiring $T$ to have the same size as $S$? Do you require not just "existence" but also that the subset of $T$ that sums to 0 has to be the "same" subset of $S$ that sums to $W$? None of these requirements are stated in the question. Don't force us to guess -- your question needs to be clear enough that everyone can understand what you are asking. $\endgroup$
    – D.W.
    Sep 14 '20 at 17:44
3
$\begingroup$

However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from the same positions) evaluates to 0? All other subsets in T should evaluate to 1.

No, this is impossible. Consider $S=\{1,2,3\}$ and $W=3$. Our set $T$ should be $\{a,b,c\}$ such that $a+b=0, c=0$ and $a+b+c=1$.

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