# 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? Commented Feb 12, 2021 at 10:02
• $POLY \overset{\Delta}{=} \{f:\{0,1\}^*\rightarrow \{0,1,\:\}^* |$ exists polynomial TM which competes $f \}$ Commented Feb 12, 2021 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.
Commented Feb 12, 2021 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}$$.