7
$\begingroup$

I am not an expert in this field, but I have read that the existence of one-way functions implies $P \neq NP$. Since there seem to be so many different definitions of one-way-functions and I have not seen a proof I wanted to ask if someone knows where to read this, or knows the proof. Please if you give a proof, also give a precise definition of which version of "one-way-function" you use. The proof can of course be detailed, the detailed, the better! :) Thanks!

$\endgroup$
6
  • 5
    $\begingroup$ Suppose, for the sake of contradiction, that $P=NP$ and there is a one-way function $f$. You know $f$ is computed by a poly-size circuit. Given $y$, can you think of a way to find $x$ with $f(x)=y$? $\endgroup$
    – Thomas
    Commented Oct 2, 2015 at 20:09
  • $\begingroup$ I guess the poly-size circuit problem is in NP, so since by assumption P=NP, we can solve the poly-size circuit problem in polynomial time and thus invert $f$ which contradicts the assumption that $f$ is one-way. But I didn't know of the connection of $f$ to the poly-size circuit problem. Do you have any reference for this? $\endgroup$
    – user35803
    Commented Oct 2, 2015 at 20:15
  • $\begingroup$ Assuming $P=NP$, there is an algorithm that takes as input a circuit computing a function $f : \{0,1\}^n \to \{0,1\}$, outputs $x$ with $f(x)=1$ if such an $x$ exists, and runs in time polynomial in $n$ and the size of the circuit. $\endgroup$
    – Thomas
    Commented Oct 2, 2015 at 21:42
  • $\begingroup$ Ok, but how does one construct an $NP$ complete problem given a one-way-function (Definition of Wikipedia)? $\endgroup$
    – user35803
    Commented Oct 3, 2015 at 8:53
  • 1
    $\begingroup$ Checking whether a given circuit has a satisfying assignment is an NP-complete problem. $\endgroup$
    – Thomas
    Commented Oct 3, 2015 at 15:05

3 Answers 3

11
$\begingroup$

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

$\endgroup$
1
  • 10
    $\begingroup$ it would be helpful to sketch out/ summarize some of the proof. $\endgroup$
    – vzn
    Commented Oct 5, 2015 at 0:30
6
$\begingroup$

If P=NP, every polytime computable 1-1 function $f$ has a polytime computable inverse: $\{(x,y) \mid \exists z\ |yz| \leq poly(|x|) \land f(yz)=x \}$ is NP. We can find a $y$ such that $f(y)=x$ by starting with the empty string as$y$ and greedily adding the following bits using this NP oracle.

$\endgroup$
5
$\begingroup$

Let $f:\{0,1\}^* \rightarrow \{0,1\}^*$ be a OWF and define $L_f = \{(x,y)\in \{0,1\}^* \times \{0,1\}^*:$ there exists $z$ such that $f(xz)=y\}$. I construct the following non-deterministic Turing machine: $A((x,y)):$"Non-deterministically guess $z$. return ACCEPT if $f(xz)=y$ and REJECT otherwise" $A$ makes a single call to $f$ which is OWF and therefore runs in polynomial time. $A$ decides $L_f$ therefore $L_f \in NP$.

Assuming $P=NP$, there exists a deterministic polynomial time decider $A'$ such that $A'((x,y)) = ACCEPT \iff A((x,y)) = ACCEPT$. Using $A'$ I construct $f'$ which inverts $f$ in deterministic polynomial time. First, I define a helper function $h:(\{0,1\}^*,\{0,1\}^*) \rightarrow \{0,1\}^*$ the following way:

$h(x,y) = $ \begin{cases} h(x0,y),& \text{if } A'(x0, y) = ACCEPT\\ h(x1,y),& \text{if } A'(x1, y) = ACCEPT\\ x & \text{otherwise} \end{cases}

$h$ is a recursive function that tries to add a single bit $b$ to $x$ in every iteration. If $A'$ accepts $xb$, that means there exists some $z$ such that $f(xbz) = y$. In this case, $h$ recalls itself with $xb$. Once $|z| = 0$ I know parameter $x$ contains the preimage of $y$ and the DTM $A'$ would reject both $(x0,y)$ and $(x1,y)$. In this case $h$ returns $x$. $h$ runs in deterministic polynomial time in $|xz|$ since at every iteration $|x|$ grows by 1 on account of $|z|$. At every iteration $h$ calls $A'$ which runs in polynomial time, making the total runtime of $h$ polynomial.

Using $h$ I define the function $f':\{0,1\}^* \rightarrow \{0,1\}^*$ such that $f'(y) = $ "Initialize $x$ to be empty and return $h(x,y)$". $f'$ inverts $f$ in deterministic polynomial therefore $f$ is not OWF, reaching contradiction. In conclusion, if there exists a OWF, then $P \neq NP$.

$\endgroup$
5
  • $\begingroup$ If P=NP, any polytime computable 1-1 function has a polytime computable inverse. The proof is not even a paragraph: $\{(x,y) \mid \exists z\ |yz| \leq poly(|x|) \land f(yz)=x \}$ is NP. We can find a $y$ by starting at empty string and greedily adding the following bits using this NP oracle. $\endgroup$
    – Kaveh
    Commented Dec 10, 2016 at 11:31
  • 1
    $\begingroup$ That's exactly what I did. $\endgroup$
    – Ben Danon
    Commented Dec 10, 2016 at 12:45
  • 1
    $\begingroup$ It was already hinted under the question. Your answer is too long for this basic question imo. Anyone who has seen a reduction from search to decision should be able to fill out the rest. $\endgroup$
    – Kaveh
    Commented Dec 10, 2016 at 13:59
  • 2
    $\begingroup$ Every point in my answer is a necessary logical step. $\endgroup$
    – Ben Danon
    Commented Dec 10, 2016 at 14:24
  • 1
    $\begingroup$ Not on this site. Have you checked help center? If someone cannot fill in the gaps like these then probably they should ask the question on our sister site Computer Science in place of here. $\endgroup$
    – Kaveh
    Commented Dec 10, 2016 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.