# reducing a decision problem to a local search problem

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

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$$.
• 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? – DS_UNI Nov 16 '18 at 10:42