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?
Best Answer
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 ...