# How to prove that existence of one-way functions implies P≠NP?

The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.

How is this proved?

Suppose that P=NP, and that $$f\colon \{0,1\}^* \to \{0,1\}^*$$ is an arbitrary function computable in polynomial time. Suppose that $$|x| = n$$, and we are given $$y = f(x)$$. We will show how to find $$z \in \{0,1\}^n$$ such that $$y = f(z)$$ in polynomial time (in $$n$$).
Using an NP oracle, we determine whether there exists $$z$$ such that $$z_1 = 1$$ and $$y = f(z)$$. If so, we set $$w_1 = 1$$, and otherwise, we set $$w_1 = 0$$. Using an NP oracle, we determine whether there exists $$z$$ such that $$z_1 = w_1$$, $$z_2 = 1$$, and $$y = f(z)$$. We set $$w_2$$ accordingly. Continuing in this way, we eventually found $$z$$ such that $$y = f(z)$$. Since we assumed that P=NP, this algorithm runs in polynomial time.