# 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 ? –  Fayez Abdlrazaq Deab Sep 3 '13 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. Sep 3 '13 at 18:12
this explanation is marvelous ... now I have better understanding of these things ... –  Fayez Abdlrazaq Deab Sep 4 '13 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 . –  Fayez Abdlrazaq Deab Sep 3 '13 at 9:20
That function is not one-way. $\;$ –  Ricky Demer Sep 3 '13 at 9:39
why not ? all algorithms can just provide correct answer of small fraction of all possible inputs ? –  Fayez Abdlrazaq Deab Sep 3 '13 at 9:42
Because it's easy to find a correct answer on any input for which there is a correct answer. $\;$ –  Ricky Demer Sep 3 '13 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". $\;\;\;$ –  Ricky Demer Sep 3 '13 at 9:52