13
$\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?

$\endgroup$
5
  • 1
    $\begingroup$ Wouldn't that immediately yield $P\neq NP$? (Unless the inverse significantly increase the length of $n$...) $\endgroup$ Commented Jun 21, 2011 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$ Commented Jun 21, 2011 at 7:15
  • 4
    $\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$ Commented Jun 21, 2011 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$ Commented Jun 21, 2011 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$ Commented Jun 21, 2011 at 12:28

1 Answer 1

3
$\begingroup$

If one adds the condition of honesty (that $|x| \leq poly(|f(x)|)$, as pointed out by Dorais in the comments), then this is precisely the question of whether (complexity-theoretic, as opposed to cryptographic) one-way functions exist. They exist if and only if $\mathsf{P} \neq \mathsf{UP}$ (Grollman & Selman and Ko). Whether $\mathsf{P} = \mathsf{UP}$ or not is a well-known open complexity question equivalent to the OQ.

That being said, there are many candidates for such functions, such as those that are used in cryptography. For example, integer multiplication is a candidate - it is known to be computable in polynomial-time, it is honest, if we restrict to multiplication of pairs $(a,b)$ where $a < b$ and $a,b$ are both prime, then it is injective, and its inverse is not known to be computable in polynomial time. Another example comes from Tensor Isomorphism: given a tensor $T \in \mathbb{F}^n \otimes \mathbb{F}^m \otimes \mathbb{F}^p$ and $g \in GL_n \times GL_m \times GL_p$, consider the function $(T,g) \mapsto (T, g \cdot T)$. This function is honest and injective, but inverting it is TI-complete. This was suggested as the basis for a bunch of cryptographic primitives in Ji-Qiao-Song-Yun.

Lastly, some results are known regarding other complexity classes, or weakening the one-to-one assumption. For example:

  1. Say that a function $f$ (not necessarily one-to-one) is "invertible in polynomial time" if there is a poly-time-computable function $g$ such that $f(g(y)) = y$ for all $y \in \text{Image}(f)$. If every honest poly-time $f$ had such an inverse, then $\mathsf{P} = \mathsf{NP}$. (Proof: consider the function $f(\varphi,x) = \varphi$ if $\varphi$ is a 3cnf formula and $\varphi(x)=T$, and otherwise $f(\varphi,x)=0$. An inverse to this function lets you compute satisfying assignments to 3cnf's.)

  2. Even if you only ask that $f$ have an inverse in $\mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ (aka $\mathsf{NPSV}_t$), if all honest poly-time $f$ have such an inverse, the polynomial hierarchy collapses to its second level Hemaspaandra-Naik-Ogihara-Selman. (Side note: this is related to one of my favorite open oracle questions. Namely, not only do we not know whether $\mathsf{NP} = \mathsf{UP} \Rightarrow \mathsf{PH}$ collapses, we don't even know whether this question requires nonrelativizing techniques. Does there exist an oracle relative to which $\mathsf{NP}=\mathsf{UP}$ but $\mathsf{PH}$ doesn't collapse to the second level? Or doesn't collapse at all?)

  3. If we instead assume surjectivity, the assumption that all onto honest poly-time functions have poly-time inverses was studied by Fenner-Fortnow-Naik-Rogers. They dubbed it "Hypothesis Q", and showed it is equivalent to a number of other complexity-theoretic statements. One of these equivalent statements is: for all $S \subseteq SAT$ such that $S \in \mathsf{P}$, there is a polynomial-time computable $g$ such that for all $\varphi \in S$, $g(\varphi)$ outputs a satisfying assignment to $\varphi$. (Note that this does not follow automatically from the usual self-reducibility of SAT, since one does not know that the self-reduction takes formulas in $S$ to formulas in $S$.)

  4. If instead of poly-time we talk about polynomial circuit size, Birget showed that such functions exist unless $\mathsf{PH} = \mathsf{\Sigma_2 P}$.

  5. For one-way functions with additional properties (such as commutativity, associativity, and a few others), their existence is related to the existence of ordinary one-way functions, see Hemaspaandra-Rothe-Saxena.

$\endgroup$

You must log in to answer this question.