I define a function
f to be one-way iff for any sufficiently large
f(x) bounded by a polynomial, but reversing it (i.e. finding such
f(x) = f(y)) has no algorithm in
P (except, maybe, a negligible probability of guessing
x was chosen truly randomly).
Clearly, no one-way function can exist if
P = NP. The question I am puzzled with is whether
P != NP would imply the existence of such a function.
To the best of my thinking, the answer is negative: even if there are problems in
NP that do not belong to
P we can't know they "reverse" some other problem in
P. Am I right?