Log in

No account? Create an account

Applicable Proofs...

We both know it's been forever since I posted on LJ. This one's too long for Twitter and doesn't mesh well with my mostly-Lisp blog. 'Nuff said.

I've started reading The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow. So far, I'm enjoying the material. However, he keeps smacking into one of my biggest math peeves: Proof is Panacea.

Before I explain that or mention how it relates to Fortnow's book, let me tell you where Numbers smacked into this peeve.

Season One, Episode Five guest-starred Neil Patrick Harris. NPH was close to a proof of the Riemann Hypothesis. The Riemann Hypothesis is closely linked to the distribution of prime numbers. Prime numbers are intimately involved in much of the encryption technology in use today (even more so back when that episode first aired).

In the episode, NPH's daughter had been kidnapped by some baddies that were demanding a complete proof of the Riemann Hypothesis as ransom. Part of the premise of the episode was that with such a proof the kidnappers would be able to decrypt any secure internet transactions. Modern civilization would fall apart.

At the time, eyelid asked me, What would happen if someone could prove the Riemann Hypothesis? My thought at the time (and still), is absolutely nothing in any sort of short timeframe beyond winning the author a Millenium Prize.

If there is anything you can do to break today's encryption schemes once you know the Riemann Hypothesis to be true, then you can already do that just by guessing that the Riemann Hypothesis is true. Sure, there is a small chance that there will be some new tool or new revelation that comes out of the manner in which the Riemann Hypothesis is proven (or falsified) that might eventually make finding particular primes easier. I consider that a small chance and only after years of delving.

It is a sad truth that many of the great proofs are non-constructive. One of the easiest ones to follow is Euclid's proof of the Infinitude of the Primes. Suppose for a moment that there aren't infinitely many primes. If that were the case, there would only be N of them for some (possibly large) number N. If you multiply all of those primes together you get a number that is divisible by every prime number. If you add one to that number, now you have a number that has remainder one when divided by any prime number. So, either this number is prime and wasn't on your list, or you missed some prime that divides into this number. It must, therefore, be impossible to have a finite list of all of the prime numbers.

What can you do now that this has been proven that you couldn't do before this was proven? You can prove things that depend on it being true, but what can you do. The answer is nothing new. You can't even name a single prime number that you should have had on your list. You can't tell whether any given number that didn't make your list is prime or not. You can't tell how many primes you might have missed. Anything you can do because we've proven there are infinitely many primes, you could have done with just the supposition (or hope) that there were infinitely many primes.

I can understand how a TV drama might ignore that inconvenient truth so it won't fizzle the tension in your plot, but I can't forgive Fortnow the same sin. Fortnow says over and over again that if you can prove that P = NP then you can do all kinds of things easily that everyone else still considers hard. You'll be able to optimally route your Travelling Salesman, you'll be able to crack my public key, you'll be able to optimally fit your stuff into the minimum number of moving truck trips, and you'll be able to play a perfect game of Tetris if you know what order the pieces will come out.

First, as does Fortnow, I consider it very unlikely that P does equal NP. Second, even if P = NP, I'd only give it about a one in fifty chance of being provable. Third, if it's provable, I'd give it a one in one thousand chance that the first proof will be constructive. Fourth, even if it is constructive, I'd only give that a one in ten chance of showing any way to find an algorithm in P to solve any given problem.

Fortnow knows way more about P vs. NP than I do. Maybe he knows something that he's not letting on about that guarantees that the only way to prove P = NP is by demonstration. If that's the case, I sure wish he'd tell me. But, I think he's either just caught up in how cool it would be if NP were P or he's just building drama by sweeping truth under the rug.