# How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

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.

• 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?
– D.W.
Sep 14 '20 at 6:21
• @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. Sep 14 '20 at 17:38
• "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?
– D.W.
Sep 14 '20 at 17:39
• @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$. Sep 14 '20 at 17:42
• 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.
– D.W.
Sep 14 '20 at 17:44

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