Post
Topic
Board Development & Technical Discussion
Re: The existence of one-way function means P!=NP
by
gaom094
on 29/01/2021, 09:41:59 UTC
Nobody ever managed to prove before whether P equals or does not equal NP. As your paper mentioned that the existence of one-way functions opens up a proof to P!=NP, let's discuss that.
if P = NP, then F P = FNP, and so any function that can be computed in polynomial time can be inverted in polynomial time, since there is a simple FNP algorithm that inverts it by nondeterministically enumerating all possible inputs.
However, it is not known whether P = NP implies the existence of one-way functions.

As NotATether said, the "randomness" of parameters should be called "arbitrary".
Yes, in this paper, we can replace "randomness" by "arbitrary" without affecting the correctness of the conclusion.