Understanding of what it means to say that a question is in NP

40 Views Asked by At

Let's say the the function $f$ can be evaluated in polytime in the size of the input $x$. Are the following problems in NP?

Is there an $x$ such that $f(x) = y$ for a particular value of $y$?

Find an $x$ such that $f(x) = y$ for a particular value of $y$?

Do either of these answers change when not all values of $y$ have a corresponding $x$?

It seems like the answer to both of these would be "yes" because your certificate is just that particular value of $x$ and then you can verify it by running $f$, but I'm not sure because the second question seems much more involved than the first.

1

There are 1 best solutions below

2
On BEST ANSWER

I have since learned that the concept of NP applies to questions that have a yes or no answer, not questions that are requesting a particular number. Therefore, my first question is in NP and the second is not.