# Minimum absolute value of subset sums of integer values

$$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$$

How to prove $$f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$$?

When $$\mathbf{POLY}\overset{\Delta}{=}\{ f:\{0,1\}^*\rightarrow \{0,1, \}^* |$$ exists polynomial TM which competes $$f \}$$

• What is Poly? Is it P? Feb 12 at 10:02
• $POLY \overset{\Delta}{=} \{f:\{0,1\}^*\rightarrow \{0,1,\:\}^* |$ exists polynomial TM which competes $f \}$ Feb 12 at 10:14
• Please don't leave clarifications in the comments. Instead, edit your question so it includes everything necessary to understand what you are asking. Then you can flag comments as 'no longer needed' once you've done that.
– D.W.
Feb 12 at 20:11

We give a Turing reduction from the $$\mathrm{SubsetSum}$$ problem. Suppose we are given a $$\mathrm{SubsetSum}$$ instance $$(A, k)$$ where w.l.o.g. $$A$$ only contains positive integers, i.e. we want to find a set $$X \subseteq A$$ such that $$\sum_{x \in X} x = k$$ and define the set $$A' = A \cup \{- k\}$$.

We want to show that $$f(A') = 0$$ if and only if $$(A, k) \in \mathrm{SubsetSum}$$:

• Suppose that $$(A, k) \in \mathrm{SubsetSum}$$. Then there exists a set $$X \subseteq A$$ such that $$\sum_{x \in X} x = k$$, i.e. the sum over the elements of $$X \cup \{-k\} \subseteq A'$$ is $$0$$, implying $$f(A') = 0$$.
• Otherwise, we have $$(A, k) \notin \mathrm{SubsetSum}$$. As $$A$$ only contains positive integers but no subset of $$A$$ sums to $$k$$ we infer that any subset of $$A'$$ sums to some nonzero value.

It follows that if $$f$$ is computable by some polynomial time DTM then $$\mathrm{SubsetSum}$$ can in turn be decided in polynomial time, showing that $$\mathsf P = \mathsf{NP}$$.

• Thanks! but I think that your answer work only in one direction, isn't? Feb 11 at 18:58
• Oh, true, I forgot that you also asked about the other one. You should try and figure that one out yourself though. Feb 11 at 19:00