How to show a language is in NP?

Question

(I reorganized my question.) We have a function $f$ mapping the integers $\{1, . . . , 2^k\}$ ONTO the integers $\{1, . . . , 2^k \}$ such that when these integers are represented in binary, and $f$ is polynomial time computable but the inverse function $f^{-1}$ is not polynomial time computable. Define a language $L =\{(x,y) | f^{-1}(x)<y\}$. Show that this language $L$ is in NP.

$f$ is surjective, so $f^{-1}$ is adjective. Since $f$ is polynomial time computable, so we can find $f(f^{-1}(x))=x$ in polynomial time, but $f^{-1}(x)$ is not polynomial time computable, how can we compare $f^{-1}(x)<y$?

Answer 1

You have already figured out that $f^{-1}(x)$ can be used as a potential NP certificate. You are just missing the crucial part in the definition of NP.

You don't have to compute the certificate, you can non-deterministically guess this certificate and verify if it is a good certificate in polynomial time. How hard or easy it is to produce such a certificate doesn't matter in NP, all that matters is its existence. Since $f$ is polynomial time computable, for any $z$, you can efficiently verify if $z = f^{-1}(x)$.

Answer 2

The value $f(x)$ is a polynomial length certificate for the language, since it has the same size as $x$, and can be checked in polynomial time by verifying that $f^{-1}(f(x)) = x$ and that $f(x) < y$.