Content deleted Content added
m Signing comment by 2A02:8070:8798:4000:80E4:FDE0:A138:9EB6 - "→Existence of one-way functions and implications to P and NP: new section" |
→Generalization: new section |
||
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-->
== Generalization ==
As defined here, one-way functions are defined so they are polynomial time, but their inverse is not. However, the same concept could be thought of more generally as functions with a strict upper bound that is a lower bound on their inverse. Is there any information about this more general problem, how it is formulated and described, it’s implications, and whether or not it has been solved?
| |||