Re:What if P = NP?
by bdhe on Friday April 01, 2011 @06:05PM
(#2398282)
> If P = NP, and someone solves any NP-complete problem, all the NP-complete problems crumble and our security is a thing of the past.
Security can still be achieved. But it will require exponential time for an honest participant (a much lesser exponent than an adversary, but still exponential time). See: http://en.wikipedia.org/wiki/Merkle%27s_Puzzles It doesn't require P!=NP.
Security can still be achieved. But it will require exponential time for an honest participant (a much lesser exponent than an adversary, but still exponential time). See: http://en.wikipedia.org/wiki/Merkle%27s_Puzzles It doesn't require P!=NP.