Let f be a polynomial-time reduction of a decision problem A to a decision problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then A $\in$ NP. However, what about the other direction? Assume that A $\in$ NP and consider the following non-deterministic algorithms to decide whether y $\in$ B:
- "Guess" non-deterministically some x.
- Verify that f(x) = y by computing f(x) in polynomial time and comparing it with y. If f(x)$\neq$y, reject.
- Check (using the polynomial-time nRAM for A) whether x $\in$ A and return the answer.
Why does this not qualify as a proof that B $\in$ NP?