1

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.

Everyone_Else
  • 289

1 Answers1

-1

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.

Everyone_Else
  • 289
  • 1
    For the first one you need an additional condition for it to necessarily be in NP: The size of the smallest $x$ if it exists needs to be bounded by a polynomial in the size of $y$. – Dan Brumleve Mar 01 '16 at 16:01
  • For example, let $f(x) = y$ whenever $x$ is a valid proof of $y$ (in ZFC, say) and $0$ otherwise. $f(x)$ can be evaluated in polynomial time (make sure $x$ is a valid proof and extract its concluding sentence). But the set of all provable statements is not in NP or even decidable if ZFC is consistent. – Dan Brumleve Mar 01 '16 at 18:41