A fascinating, if slightly abstruse, article by Lee Gomes appeared in the Digital Tools column in Forbes’ March 29 edition under the title “Computing’s Killer Problem.” Its implications are fascinating, so I’ll try to synthesize here. For the full article, go here.

Basically, Gomes posits the notion that much of what we do with computers, including basic Internet and transactional security, is based “not on anything we know for sure, but on essentially just a good guess.” It starts with a fundamental computer science problem known as P=NP. The question of course is whether P equals NP, but the explanation of each is a bit tricky, so hang in there. And by the way, solve it, and you’re eligible for a $1 Million reward. Here goes…

P stands for the collection of math problems a computer can solve in a reasonable amount of time. But, being defined by Math Guys, it’s a bit more specific than that. P stand for Polynomial. A problem that gets just a little harder as the numbers get bigger is deemed solvable in polynomial time. The opposite if Exponential, where the time to solve “quickly grows unreasonably large.”

NP stands for problems that can be *verified* in a reasonable length of time. Thus, the equation asks if P and NP are the same. Gomes gives the example of factoring. It’s easy to verify that two numbers multiplied together produce a third; 10 x 20 = 200 for example. This is true even for very large numbers – it’s easy. But going the other way, as in starting with the end number and finding the factors that make it up, can take a large amount of time, especially if the number is large enough. With a large enough number, it could take trillions of years, he notes.

I’ll spare some complexity that you can read in his article, but the bottom line is that most math researchers think that P and NP are *not* the same. Why does this matter? Because encryption routines, for example, “hang on the difficulty of factoring large numbers,” where no fundamental shortcut has ever been found (and math geeks have been looking for centuries). Therefore, encryption routines can be presumed to be safe in terms of taking enormous time to solve.

But what if they’re wrong? What if P=NP? Then problems on the NP side (quick verification) are also on the P side (quick finding of a solution). This would mean in theory that a quick factorization was possible after all – you’d just need to be clever enough to find it! And that would put security and encryption on some very unsure footing, wouldn’t it?

Gomes claims no need for panic, since “most experts think P and NP aren’t the same.” But no one knows for sure. Certain people could lose sleep over this.

On the upside, researchers have also uncovered the fact that a large group of hard computer problems, despite external appearances, turn out to be essentially similar. Examples include mapping the most efficient route for a travelling salesperson and a protein folding problem to predict the shape of a molecule. A solution to one apparently would work for the other according to a Northwestern Univ. professor.

But only if P=NP -– precisely what we don’t know. Dare I say it? Go figure.

on June 27, 2010 at 9:09 pm |rjliptonI agree. Take a look at my ideas at

http://rjlipton.wordpress.com/

on January 18, 2011 at 8:20 am |PSSI’s Blog: 2010 in review « The PSSI Blog[…] The Trouble With Large Numbers, And What It Means to Your Credit Card Security April 2010 1 comment 5 […]