FYI.

This story is over 5 years old.

Tech

New Proof Answers Computer Science's Greatest Mystery, Keeps Our Secrets Safe

h4. Or, that Some Problems Can't Be Solved (In a Reasonable Amount of Time)The news over the weekend that P! does not equal NP after all might not have been cause for a celebratory calculator-watch-off. If you ever wanted to hack the security systems...

Some Problems Can't Be Solved (In a Reasonable Amount of Time)

The news over the weekend that P! does not equal NP after all might not have been cause for a celebratory calculator-watch-off. If you ever wanted to hack the security systems of every computer in the world – or win a million dollars for your proof – the alleged proof should really bum you out.

Not that many people really believed that P! equaled NP anyway. In a 2002 poll, only nine out of 70 mathematicians said they thought that was the real deal, and several of those admitted they were only trying to be contrary.

Advertisement

Still, like a very complex albatross, the equation has hung around the pasty necks of math and computer science for decades, worrying data security companies like Symantec – whose cryptography depends upon certain problems being hard to solve – and, more recently, taunting mathematicians as a Clay Institute Millennium Prize problem, one of the seven that can earn its solvers a million dollar prize.

Once, when he traveled to an alternate dimension, the equation even haunted Homer Simpson.

P equals whatnow?

The equation touches on a question central to the field of computational complexity : How long does it take a computer to execute a given algorithm, a method for computing a set of numbers? This isn't a question of time, not just, but rather of how many elements the algorithm must deal with, and how many steps it takes to solve.

So imagine that an algorithm with an execution time proportional to N takes one second to perform a calculation involving 100 numbers. For an algorithm whose execution time is proportional to N^3, the computation takes almost three hours. The discrepancy grows by a constant. But an algorithm whose execution time is proportional to 2^N would takes 300 quintillion years to calculate. And the larger N gets, the longer it takes to solve a problem.

And here's the question that P! equals NP asks: even if we know one of those problems yields the correct answer, are there actually efficient ways of solving these problems, even with the fastest computers in the world?

Advertisement

"If you want to build a bridge with a mile long span, that's a problem," Richard Lipton, a professor of Computer Science at Georgia Tech, a veteran computational theorist and editor of a blog about the problem, told Motherboard. "Want to build a two-mile long span? The time it takes to solve the problem goes up by a constant factor. But there are lots of problems that arise naturally that don't seem to be doable in polynomial time."

One is the eighty-year-old traveling salesman problem. Given a list of cities and the distances between each of them, the task is to find a shortest possible tour that visits each city exactly once. It sounds hard, and it's harder than it sounds.

Another set of problems that are computationally inefficient are the ones that encrypt, well, every thing on the internet and every computer. If you could solve the NP-complete problem 3-SAT, for instance, you would then know how to break many existing cryptosystems such as Public-key cryptography, which is used for economic transactions online, and Triple DES, used for transactions between banks. "You are relying on the fact that factoring a number or braking a scheme can't be done in polynomial time."

Another example problem: winning Minesweeper. No, really.

Here's another way of thinking about it (taken, obviously, from an old math web page):

given n floppy disks each of size x and m computer files of sizes y1, y2, y3, … ym, is it possible to copy all of the files to the floppy disks given?

Advertisement

It's possible sometimes and it's not possible other times. What we need is a computer program (or algorithm) that will give the answer in all cases – again, within a reasonable amount of time, or polynomial time.

The Proof

The new proof, by Vinay Deolalikar, a researcher at HP, has yet to be examined, but given the interest in the problem – and the money at stake – it will be picked apart carefully. And even if it's not correct, Lipton is confident the 100-page proof will leave a mark on mathematics.
"Proofs not only confirmed what people knew," says Lipton. "They're hard problems. They almost always give new insight into their areas.

"[With his proof, Andrew] Wiles impacted number theory – his technology methods and insights revolutionized that field. [With the Poincare conjecture], Perlman changed the way people think about topology."

To address the P versus NP problem, Deolalikar deployed statistical physics. The hope is that approaches like this will promote the continued cooperation of computer scientists, mathematicians and physicists, and even if they're from corporate research labs, not universities.

And clearly, says Lipton, the proof will serve as a good advertisement for radical thinking.

"This will encourage other people to be more open and talk about some ideas they've had, and hasten the solutions to some of these questions.

"Computational complexity is not as good at throwing ideas out there. Independently of whether its successful or not, we should be doing more adventurous stuff."

Some attempts have been made to show that P! could actually equal NP. But these approaches depend upon quantum computing, a concept that exploits the behavior of atoms to create highly advanced computers. And Lipton says that the results could be "strange." "If quantum could prove the salesman problem, something strange could happen. There would be some strange consequence." Comforting.

But he's also pretty darn certain the proof's right. And if he's wrong, and someone proves that P! does equal NP, forget about the death of privacy, or whatever information Internet companies have on you: proving the equation right could break open all of our secrets. "That," says Lipton, "could be huge."

Feast your eyes on the proof paper here, and check out Richard Lipton's site, and get the T-shirt.