[Cryptography] P=NP on TV

Ray Dillinger bear at sonic.net
Tue Oct 8 21:18:02 EDT 2013


On 10/07/2013 05:28 PM, David Johnston wrote:
	
> We are led to believe that if it is shown that P = NP, we suddenly have a break for all sorts of algorithms.
> So if P really does = NP, we can just assume P = NP and the breaks will make themselves evident. They do not. Hence P != NP.

As I see it, it's still possible.  Proving that a solution exists does
not necessarily show you what the solution is or how to find it.  And
just because a solution is subexponential is no reason a priori to
suspect that it's cheaper than some known exponential solution for
any useful range of values.

So, to me, this is an example of TV getting it wrong.  If someone
ever proves P=NP, I expect that there will be thunderous excitement
in the math community, leaping hopes in the hearts of investors and
technologists, and then very careful explanations by the few people
who really understand the proof that it doesn't mean we can actually
do anything we couldn't do before.

				Bear


More information about the cryptography mailing list