11
$\begingroup$

According to this, the existence of a one-way function proves P ≠ NP. What is the proof of this?

One way to show this is that if P = NP, then any function is easy to invert. P and NP are about decision problems though, not computation problems.

(Basically, my question is about how statements about decision problems relate to computational problems.)

$\endgroup$
  • 1
    $\begingroup$ I don't have an actual proof, but I suppose on a non-deterministic machine you could easily invert a one-way function $f$: Given an image $f(x)=y$, simply use non-determinism to guess a pre-image $x'$. Test if the guessed pre-image is in fact a pre-image, i.e., whether $f(x')=y$ and if so output $x'$. $\endgroup$ – Guut Boy Sep 10 '16 at 15:54
  • 1
    $\begingroup$ If P=NP then decision and search problems are equivalent. This is because decision=search for NP-complete problems. $\endgroup$ – Yehuda Lindell Sep 10 '16 at 17:54
  • $\begingroup$ @YehudaLindell What's the proof of that? $\endgroup$ – PyRulez Sep 10 '16 at 17:55
  • 2
    $\begingroup$ You can search on the web. But let's do Hamiltonicity for example. Assume that you have an oracle O who answers whether or not a graph contains a Hamiltonian cycle. You can take the graph G and remove an edge, and then ask the oracle if the graph has a Hamiltonian cycle. If no, then you know that this edge is needed so you return it. If yes, then you leave it out and remove another edge. You continue this way until you are left with a single cycle. $\endgroup$ – Yehuda Lindell Sep 10 '16 at 17:58
14
$\begingroup$

It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist:

Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $x^\ast$ is a prefix of some $x$ satisfying $f(x) = y$. $L$ is in $\mathit{NP}$ because $x$ itself is a witness (up to minor formal details; see this question too) we can use to verify the pair in only polynomial time—recall that a one-way function can be computed in poly-time.

But we have $P = \mathit{NP}$, and we can use a decider $D$ for $L$ to "invert" $y$. Receiving the input $(y, 1^n)$ ($n$ being the safety parameter), start with the pair $(\varepsilon, y)$, i.e. with the empty word as a prefix, and use $D$ to incrementally add bits to the prefix part until you obtain $(x,y)$ with $f(x) = y$. Such an algorithm runs in poly time because it is guaranteed there exists an inverse image to $y$ of length at most $n$. It follows that $f$ is not one-way, and we have a contradiction.


Regarding your question about the relation between decision problems and computational ones: the whole point of the $P = \mathit{NP}$ dilemma is answering whether computing a solution is as hard as simply verifying it or not. This is because non-determinism virtually allows us to "cheat" and circumvent wasting any time in computing the answer; we only need to guess it and check whether our guess was correct or not.

An interesting consequence of the statement above is that the assumption of one-way functions is actually stronger than $P \neq \mathit{NP}$. This is in line with the famous hierarchy of cryptographical assumptions known as Impagliazzo's five worlds.

$\endgroup$
  • 2
    $\begingroup$ For the inexperienced reader of proofs: "X implies not Y" is equivalent (by contraposition and double-negation) to "Y implies not X". $\endgroup$ – SEJPM Sep 10 '16 at 20:18
  • 1
    $\begingroup$ You write: "L is in NP because x itself is a witness we can use to verify the pair in only polynomial time." But for being an NP-witness, the length of x should be polynomially bounded in the lengths of y and y^*. How is this guaranteed? $\endgroup$ – Alexis Dec 17 '18 at 13:24
1
$\begingroup$

Sounds like a homework problem. There is a solution here.

Informally, define a language L = { (x', y) s.t. x' <= x and f(x) == y }. Basically, it says x' is a prefix of x, and x is a preimage of y.

It's easy to see L is in NP, because when given x' and y, you can append bits to x' until it reaches x, then you have successfully verified. This only needs polynomial time on a nondeterministic TM.

If P == NP, then L is in P. This means, when given x' and y, you can tell in polynomial time, whether it's possible to append bits to x' so that x' finally becomes a preimage of y. Then you can start from an empty string, try appending 0 and do a test, try appending 1 and do a test, at least one of them will return true because empty string is surely a prefix of x. In the following rounds, the string x' is always a prefix of x because you know whether you should add 0 or 1. Finally x' will become x. Congrat: You have found x, which is a preimage of y, in polynomial time. This reverts f.

$\endgroup$
  • $\begingroup$ You write: "It's easy to see L is in NP, because when given x' and y, you can append bits to x' until it reaches x, then you have successfully verified. This only needs polynomial time on a nondeterministic TM." But how do you guarantee that you only need to add a polynomial number of bits when moving from x' to x? $\endgroup$ – Alexis Dec 17 '18 at 13:25
  • $\begingroup$ @Alexis Think like n = |x| and x' really goes from length 0 to n. This is clearly polynomial in n. $\endgroup$ – Cyker Dec 17 '18 at 13:50

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.