Revision as of 06:57, 11 April 2021 edit 2605:a601:a927:1900:954b:b1dc:875c:d6b8 (talk) →Generalization: new section ← Previous edit		Revision as of 02:11, 10 April 2022 edit undo PolyCreator (talk \| contribs) 70 edits →Existence of one-way functions and implications to P and NP Next edit →
Line 219: On the one hand, the article states "[...] their existence would prove that the complexity classes P and NP are not equal [..]", but on the other hand also in an other section "The existence of one-way functions also implies that there is no natural proof for P≠NP". Are both implications true? If yes, what is the point of ever presenting the second one without the first one? <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/2A02:8070:8798:4000:80E4:FDE0:A138:9EB6\|2A02:8070:8798:4000:80E4:FDE0:A138:9EB6]] ([[User talk:2A02:8070:8798:4000:80E4:FDE0:A138:9EB6#top\|talk]]) 22:46, 7 February 2020 (UTC)</small> <!--Autosigned by SineBot--> I have removed the latter ("The existence of one-way functions also implies that there is no natural proof for P≠NP") because it is ambiguous. The existence of OWF implies that P≠NP directly which is stronger than saying no natural proof exists (the statement is relying on the fact that OWF implies the existence of PRF which in turn implies that no natural proof exists). == Generalization ==

Talk:One-way function: Difference between revisions