Must an algorithm that decides a problem in NP also produce a solution?
I think I have a basic misunderstanding in the definition of a decision problem.
It's widely believed that a constructive proof of P=NP with a practical implementation would break all modern cryptography, for example:-
- https://security.stackexchange.com/questions/12802/how-will-security-need-to-be-changed-if-p-np
- http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
I'm not sure I understand why.
For example, 3-SAT is NP-Complete. So if we had an algorithm that could decide satisfiable or unsatisfiable in polynomial time, we could prove P=NP. Correct?
That doesn't mean we need an algorithm that can find a solution that satisfies the input, only one that can decide whether or not a solution exists, correct?
Or, equivalently, using Diffie-Hellman key exchange (quoted from wikipedia because I don't have enough rep to post more than 2 links):-
- Alice and Bob agree to use a prime number p and base g
- Alice chooses a secret integer a, then sends Bob A = g^a mod p
- Bob chooses a secret integer b, then sends Alice B = g^b mod p
- Alice computes s = B^a mod p
- Bob computes s = A^b mod p
- Alice and Bob now share s.
Clearly if Eve could calculate a and b from A and B, that would be problematic, but a proof of P=NP would only guarantee the existence of an algorithm that given A, B, g, and p could decide whether or not a and b exist such that A^b mod p = B^a mod p. Would that be so problematic?
To express my question more generally:-
Must an algorithm that decides a problem in NP also be able to construct a solution for that problem which can then be verified in polynomial time?
Would an algorithm that decides (but does not construct a "solution") an NP-complete problem in polynomial time be sufficient to prove P=NP?
Would such a proof have any impact on cryptography at all?
Or have I misunderstood something basic?
If you could decide SAT problems in polynomial time, then you could also find a solution (for those instances that have them) in polynomial time.
Namely, if Boolean expression $A$ is satisfiable and $x$ is a variable appearing in $A$, choose one of the expressions $A|_{x=T}$ and $A|_{x=F}$
(obtained by setting $x$ to "true" or "false" respectively) that is satisfiable (at least one must be). Recurse until assignments for all variables have been found.
This extends to all problems in NP that can be reduced to SAT in such a way that a solution to the SAT problem generates (in polynomial time) a solution to the original problem. Most of the classical cases of NP-completeness are of this type.
In your example, we need to generalize a little bit, from the problem
Given $A,B,g,p$, do there exist $a,b$ such that ...
to
Given $A,B,g,p$ and $a_0, b_0, n$, do there exist $a,b$ such that $a \equiv a_0 \mod 2^n, b \equiv b_0 \mod 2^n$, and ...
Must an algorithm that decides a problem in NP also be able to construct a solution for that problem which can then be verified in polynomial time?
No, but a solution can be easily derived using the decision procedure for NP problems because all "natural" NP-complete problems seem to be downward self-reducible and all NP problems can be reduced to NP-complete problems.
Would an algorithm that decides (but does not construct a "solution") an NP-complete problem in polynomial time be sufficient to prove P=NP?
Yes. P and NP are classes of decision problems. A binary yes/no answer is all that is required for decision problems. Thanks to self-reducibility a decision procedure is all that's needed to construct a solution as well.
Would such a proof have any impact on cryptography at all?
Maybe. If the degree of the polynomial degree required to solve NP-complete problems is large in the worst case, then decrypting conventionally encrypted strings might still turn out to be hard, just not exponentially so. If the degree required is small then one-time pads are going to enjoy a renaissance.