9
$\begingroup$

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.

Are there functions $f$ that are computable in polynomial time but whose inverse is known not to be computable in polynomial time?

Does the situation change if we drop the one-to-one requirement and define the inverse as, say, min$(f^{-1})$? How about if we change the complexity class in question?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Wouldn't that immediately yield $P\neq NP$? (Unless the inverse significantly increase the length of $n$...) $\endgroup$ – darij grinberg Jun 21 '11 at 7:07
  • $\begingroup$ Known? Don't know. Unlikely to be known? Try an appropriate encoding that computes the encoded equivalent of f(G,k,p) = G if p is a Hamiltonian path through G of length at most k, and 0 otherwise. There are probably ways to tweak this to get something 1-1. Also, you can probably get something similar for most interesting complexity classes. Gerhard "Email Me About System Design" Paseman, 2011.06.21 $\endgroup$ – Gerhard Paseman Jun 21 '11 at 7:15
  • 3
    $\begingroup$ The concept is closely related to that of a one-way function, whose existence would imply $\mathrm{P}\ne\mathrm{NP}$. Link: en.wikipedia.org/wiki/One-way_function $\endgroup$ – Jesko Hüttenhain Jun 21 '11 at 9:06
  • 4
    $\begingroup$ Note that the definition of one-way function on Wikipedia is missing an often overlooked key requirement: honesty - that the length of the output must be nearly equal to some polynomial of the length of the input. As Joel's example shows, this requirement is essential... $\endgroup$ – François G. Dorais♦ Jun 21 '11 at 11:39
  • 2
    $\begingroup$ So it appears that, short of a proof of $P\neq NP$, we will have only dishonest answers to this question! :-) $\endgroup$ – Joel David Hamkins Jun 21 '11 at 12:28

Your Answer

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