# P vs NP and OWFS

It is known (simple HW exercise) that:

If P = NP, that OWFs (one way functions) can not exist.

It is also known that there is a Universal OWF: namely, there is a function f: s.t. if any OWF exists, then f is a OWF. [This is a standard result of concatenating many functions.]

Question: Is the following question open: (P != NP) => (OWFs exist) ?

Thanks

-

The claims made in your answer would seem to be statements of expectation, rather than mathematically proved assertions. For example, you say that "$P\neq NP$ does not imply anything...", but of course, if $P=NP$ happens to be true, an open question, then $P\neq NP$ would imply everything (as a false statement implies anything). In particular, the claim in your quotation that $P\neq NP$ is not a sufficient hypothesis is not actually proved there, for to prove that $P\neq NP$ is not a sufficient hypothesis for anything would imply that it is not false, and thus would settle $P$ versus $NP$. – Joel David Hamkins Oct 20 '11 at 17:48
Perhaps it is more accurate to say that $P\neq NP$ alone does not imply the existence of one-way functions? Or, that $P\neq NP$ is consistent with the existence of one-way functions and also consistent with the non-existence of one-way functions? My understanding is that the exact manner in which $P\neq NP$ determines the existence of one-way functions. Roughly, if NP problems are hard only in the worst-case but easy on average (for appropriate definitions of hard, easy, and average), OWF don't exist; if NP problems are hard on average, OWF may (but are not guaranteed to) exist. – mhum Oct 20 '11 at 20:05
I guess the unspoken assumption which should be spoken is "given our current knowledge". That is to say, as far as I know, we do not yet have any additional results that when combined with $P \neq NP$ implies either the existence or non-existence of one-way functions. Results in this line of investigation would likely be very interesting. – mhum Oct 20 '11 at 20:54