4
$\begingroup$

Wikipedia:

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

How is this proved?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is NP oracle the same as polynomial-time NP-complete algorithm? Or what is it? $\endgroup$
    – porton
    Apr 22 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$ Apr 22 at 20:48
  • $\begingroup$ What does the sub-index represent here? $\endgroup$
    – kelalaka
    Apr 23 at 21:45
  • 1
    $\begingroup$ The index represents individual bits. $\endgroup$ Apr 23 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.