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

  • 1
    $\begingroup$ What is Poly? Is it P? $\endgroup$
    – xskxzr
    Feb 12 at 10:02
  • $\begingroup$ $POLY \overset{\Delta}{=} \{f:\{0,1\}^*\rightarrow \{0,1,\:\}^* |$ exists polynomial TM which competes $f \}$ $\endgroup$ Feb 12 at 10:14
  • $\begingroup$ 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. $\endgroup$
    – 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}$.

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

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.