Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states:

If a PLS problem is NP-hard then NP = P

So assuming L is a PLS problem (polynomial local search problem) that is NP-hard, then every NP problem can be reduced to L.

Usually if $P_1$ is reducible to $P_2$ (being two decision problems) then there is a polynomial time function $f$ such that:

$I_1$ is a positive instance of $P_1$ $\qquad$ if and only if $\qquad$ $f(I_1)$ is a positive instance of $P_2$

However I'm not completely sure how would a reduction from a decision problem to a local search problem be.

I guess my question is: if $P$ is a decision problem which is reducible to the problem $L$, mentioned above, with the polynomial time function (or procedure) $g$ then complete the sentence:

$I$ is a positive instance of $P$ $\qquad$ if and only if $\qquad$ $g(I)$ is ....................


1 Answer 1


To compare search problems, polytime many-one reductions work as follows: $A$ is reducible to $B$ if there are polynomial-time computable functions $f$, $g$ such that for any $A$-instance $x$, if $y$ is a $B$-solution to $g(x)$, then $f(x,y)$ is an $A$-solution to $x$.

We can view decision problems as special cases of search problems with unique binary answers, but note that the reduction notions disagree. In particular, we cannot really see the difference between yes and no instances in the search problem view.

  • $\begingroup$ so let me check if I got this correctly: if $A$ is a decision problem, then the $A$-solution $f(x, y)$ is either 1 or 0, meaning that if the search problem $B$ is solvable in polynomial time then both YES and NO instances of $A$ are recognisable in polynomial time , do you think this statement makes sense? $\endgroup$
    – DS_UNI
    Nov 16, 2018 at 10:42
  • $\begingroup$ @DS_UNI Indeed. $\endgroup$
    – Arno
    Nov 16, 2018 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.