We know that If there exists a one-way function, then P ≠ NP. Why can we not conclude that if P ≠ NP, then there exists a one-way function? Is there a polynomial time computable function that is hard to invert in the worst case and isn't one-way?
Why can we not conclude that if P ≠ NP, then there exists a one-way function?
Because so far no one has been able to prove this statement, see here.
The statement "if one-way functions exist, then $P \neq NP$" is an implication, which just goes one way. If we build the contrapositive, we get "if $P = NP$, then one-way functions don't exist".
On the list of logical fallacies, we can find:
- Affirming the consequent, which is basically just building the converse (turning around the direction of the implication).
- Denying the antecedent, which just is an inverse of both sides of the implication.
Those are (more or less) common errors regarding logic, and only the contrapositive does not change the actual meaning of the statement. Both inversion and conversion alone do not preserve the meaning - and thus are invalid if you want to prove a statement.
Is there a polynomial time computable function that is hard to invert in the worst case and isn't one-way
Any NP-complete search problem gives you a candidate for that. That is exactly the difference between search problems in the class NP and one-way functions: The former are defined with regard to the worst-case and the later are defined for the average-case. This is also why NP-complete problems are less interesting in cryptography, where it can be not enough if only the worst-case of a problem is hard.