2
$\begingroup$

At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases:

Let $INV_1$ be the operator that maps a one-to-one function $f:[0,1]\rightarrow [0,1]$ to its inverse function $f^{-1}$. Then $INV_1(f)$ is polynomial-time computable for all polynomial-time computable, one-to-one real functions $f$ on $[0,1]$.

And for two dimensional cases:

Let $INV_2$ be the operator that maps a one-to-one function $f:[0,1]^2\rightarrow [0,1]^2$ to its inverse function $f^{-1}$. Then $P=NP$ implies that for all polynomial computable, one-to-one real functions $f$ on $[0,1]^2$, $INV_2(f)$ is polynomial-time computable, and this in turn implies $P=UP$.

How is the one-dimensional case derived? And how can the two-dimensional case be extended to n-dimensions?

$\endgroup$
  • 1
    $\begingroup$ What does the book say? $\endgroup$ – Raphael Jul 31 '14 at 22:13
2
$\begingroup$

In 1-dimensional case, the function has to be strictly-monotone. Given $y_n$ do a binary search to find $x_n$.

If $\mathsf{P} = \mathsf{NP}$, given $y_n$ we can guess $x_n$ and then verify that $f(x_n) = y_n$. The dimension doesn't matter for this part.

For the other part, that is, if $INV_d$ is polytime then $\mathsf{P} = \mathsf{UP}$, we can reduce it to $INV_2$ by noting that every 2-dimensional function can be extended to a $d$-dimensional one by letting other coordinates map as identity. So for $d'<d$, $INV_d$ being polytime computable implies that $INV_{d'}$ is also polytime. Therefore $INV_d$ being polytime implies that $INV_2$ is polytime and therefore $\mathsf{P}=\mathsf{UP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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