# Polynomial solutions, one less

Let $$L$$ be a language in the class $$FP$$ of all polynomial-time solvable problems.

The class $$FP$$ is defined by having a TM $$M$$ s.t. for any $$x$$ it computes in polynomial time a $$y$$ s.t. $$(x,y)\in L$$. Note several $$y$$s may occur, the TM is required to return one, if one exists. It doesn't matter which one.

Now lets assume that for a certain $$x_0$$ we have both $$y_a,y_b$$. What if we define:

$$L'=L\backslash \{(x_0,y_a)\}$$

We remove one of these solutions (There may be more than two; at least two). Could we prove/disorove that $$L'$$ is in $$FP$$?

I am having a hard time here as $$M$$ the TM acts like a black box. I don't see how can I alter its way of work to ignore $$y_a$$ and therefore go to $$y_b$$.

• "for a certain $x_0$" Do you mean for all $x_0$? Otherwise, we can just define $M'$ which returns $y_b$ if the input is $x_0$ and otherwise runs $M$.
– JiK
Commented May 27 at 13:36

Suppose $$L = \{(G_x, Y) \mid Y$$ is the maximum or minimum vertex cover of $$G_x\}$$. This satisfies your requirements. Now let for $$G_{x_0}$$, we discard $$Y_a$$ as the maximum vertex cover (which is all vertices in it), and we are thus left with $$Y_b$$ the minimum vertex cover. Now as we know minimum vertex cover problem can not be solved in polytime unless $$P = NP$$, your TM can not compute $$Y_b$$ in polytime.