I have a question from a test that I failed to pass, I failed to do the question.
Let A and B have two languages so that there is a reduction function f: $A\leq _pB$. Suppose that $A \in NP$. We will mark the verification algorithm for A in $M_A$. We will now provide a verification algorithm showing that $B \in NP$.
Given a possible input y to problem B, we will non-deterministically guess the x string.
If there is $f(x) \neq Y$
2.1. Reject y.
3.1. Run $M_A(X)$ and return like it
You must prove / disprove his correctness by choosing the appropriate claim. Determine which of the following statements is correct.
- The verification algorithm is incorrect because the function f is not necessarily surjective. Therefore there may be a situation where the input is possible y for problem B so that $y \in B$ does not exist x so that $f (x) = y$, then the above algorithm will reject it while it is supposed to receive
- The verification algorithm is incorrect because the function f is not injective. This can be a situation where two different values $x_1 , x_2$ are sent to the same y, and then the verification algorithm does not know which one to choose
- Although the verification algorithm is correct, it is not polynomial
- The verification algorithm is polynomial and correct
- None of the above claims are true
I did not understand why the algorithm could be wrong. The algorithm must be polynomial, because it is written that there is a polynomial reduction. In terms of correctness, I do not see where there can be a problem, there is a problem A that is reduced to another problem B, and in this way B can also be solved with the help of A.
I think the answer should be 4, but I'm not sure.