# One-way function and $EXP$

All examples of one-way functions I have see till now are closely related to the assumption that $NP\neq P$ (or even weaker ones, such as $UP\neq P$), but why not considering the theorem $P\neq EXP$?

In particular, why not building functions that in one way are in the class $FP$ and the inverse function computable in $FEXP$ (the class of functions extending the class $EXP$)?

If $P=NP$, then any one-way function can be inverted. Any one-way function can be inverted using non-deterministic polynomial time. Therefore, the assumption that $P\ne NP$ is necessary (but maybe not sufficient).

• this is not complete answer ! you just said that we use the assumption that $NP\neq P$ ! but even if $P=NP$ this not immediately correct that we can easily invert one way functions , my question is asking why not use other classes of complexity to provide one way functions ? Commented Sep 3, 2013 at 9:32
• "even if $P=NP$ this not immediately correct that we can easily invert one way functions" - Yes it is. If $P=NP$, all one-way functions can be inverted in polynomial time. This is a simple theorem. (Remember, a one-way function must be computable in the forward direction in polynomial time. This means if you have a guess at the inverse, you can check whether your guess is correct in polynomial time. That in turn means that finding the inverse is a problem in $NP$: it's a problem whose solution can be verified in polytime, which is basically the definition of $NP$.)
– D.W.
Commented Sep 3, 2013 at 18:12
• this explanation is marvelous ... now I have better understanding of these things ... Commented Sep 4, 2013 at 8:45

$UP \neq P$ is not a weaker assumption than $NP \neq P$. It is straightforward to show that if one-way functions exist then $NP \not\subseteq BPP$. For all functions $f$ in $FP$, $f^{-1} \in FEXP$ to the extent that $f^{-1}$ makes sense.

• you suggest that we can't build function like I said ? then this not form any proof . happens that one of the basic functions we know the "one time pad" function : given a natural number ,$n$, output the two number that I've added that get this number . this function is one way because you can add numbers very quickly but the other side is not even computable ! then my question have enough sense . Commented Sep 3, 2013 at 9:20
• That function is not one-way. $\;$
– user991
Commented Sep 3, 2013 at 9:39
• why not ? all algorithms can just provide correct answer of small fraction of all possible inputs ? Commented Sep 3, 2013 at 9:42
• Because it's easy to find a correct answer on any input for which there is a correct answer. $\;$
– user991
Commented Sep 3, 2013 at 9:43
• Reread the definition. $\:$ $w$ is a correct answer if and only if $f(w) = f(x)$. $\:$ It would be sufficient to have $w=x$, but that is not necessary. $\:$ I don't understand the part of your previous comment that is after "one time pad". $\;\;\;$
– user991
Commented Sep 3, 2013 at 9:52