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

  • 1
    $\begingroup$ The answer is 1. The algorithm as written is not even guaranteed to halt. $\endgroup$
    – Steven
    Jul 25 at 13:45
  • 1
    $\begingroup$ @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. $\endgroup$
    – Steven
    Jul 25 at 14:03
  • 1
    $\begingroup$ I'm talking about a verifier-perspective. From a non-deterministic TM perspective, I totally agree with you. $\endgroup$
    – nir shahar
    Jul 25 at 14:04
  • 1
    $\begingroup$ @nirshahar. I see. I was talking about the non-deterministic algorithm given in the question. $\endgroup$
    – Steven
    Jul 25 at 14:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 25 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.