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

  • $\begingroup$ "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$. $\endgroup$
    – JiK
    Commented May 27 at 13:36

1 Answer 1


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.


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.