The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.
How is this proved?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Apr 22, 2021 at 14:45
-
$\begingroup$ Is NP oracle the same as polynomial-time NP-complete algorithm? Or what is it? $\endgroup$– portonCommented Apr 22, 2021 at 19:54
-
$\begingroup$ It's a machine that can solve NP problems. If P=NP, then you can simulate an NP oracle with a standard Turing machine. $\endgroup$ Commented Apr 22, 2021 at 20:48
-
$\begingroup$ What does the sub-index represent here? $\endgroup$– kelalakaCommented Apr 23, 2021 at 21:45
-
1$\begingroup$ The index represents individual bits. $\endgroup$ Commented Apr 23, 2021 at 21:48