# Reduction from problem A to another problem B

I have a question from a test that I failed to pass, I failed to do the question.

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

1. Given a possible input y to problem B, we will non-deterministically guess the x string.

2. If there is $$f(x) \neq Y$$

2.1. Reject y.

1. Otherwise

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.

1. 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
2. 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
3. Although the verification algorithm is correct, it is not polynomial
4. The verification algorithm is polynomial and correct
5. 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.

Intuitively $$A \le_p B$$ means that a polynomial-time algorithm for $$B$$ can be used to solve $$A$$ in polynomial-time, not vice-versa.
That said $$f$$ is not required to be surjective, think for example of $$A=\Sigma^*$$ and $$B=\{0,1\}$$. Suppose that $$f(x) = 0$$ (i.e., $$f$$ is the constant function). Simulate the algorithm with $$y=1$$ and notice that it will reject since there is no $$x$$ such that $$f(x)=1$$.
Moreover, the (non-deterministic) algorithm must run in polynomial time. While you know that $$|f(x)| \le \textrm{poly}(|x|)$$, no upper bound for $$|x|$$ can be given as a function of $$|f(x)|$$. To run in polynomial time, the algorithm must (non-deterministically) guess strings $$x$$ of length $$|x| \le p(|y|)$$, for some polynomial $$p$$. What if $$x$$ exists but $$|x|>p(|y|)$$? In short, how do you know when to stop guessing $$x$$?
• @nirshahar. Consider my example with $A=\Sigma^*$, $f(x)=0$ and $y = 1 \in B = \{0,1\}$. Why does the algorithm halt? It will keep trying strings $x$ forever. Trying all strings of length $\ell$ requires $\ell$ steps even on a non-deterministic Turing machine. Jul 25 at 14:03
• Algorithm $\mathcal{A}$ is not even guaranteed to halt. $\mathcal{A}'$ always halts but still doesn't answer correctly. I hope this clarifies the matter. Jul 25 at 14:29