0
$\begingroup$

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

$\endgroup$
0

2 Answers 2

0
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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