Timeline for P vs NP and OWFS
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 24, 2017 at 19:46 | comment | added | Steven Stadnicki | It seems as though the 'best' outcome is an oracle with respect to which $P\neq NP$ and yet OWFs don't exist. That wouldn't show anything about 'our' world, but it would serve to show the relative independence of the two notions. | |
| Oct 20, 2011 at 20:54 | comment | added | mhum | 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. | |
| Oct 20, 2011 at 20:05 | comment | added | mhum | 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. | |
| Oct 20, 2011 at 17:48 | comment | added | Joel David Hamkins | 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$. | |
| Oct 20, 2011 at 17:19 | history | edited | mhum | CC BY-SA 3.0 |
added 2 characters in body
|
| Oct 20, 2011 at 4:22 | history | answered | mhum | CC BY-SA 3.0 |