Some Problems Can't Be Solved (In a Reasonable Amount of Time)
Advertisement
P equals whatnow?
Advertisement
Advertisement
The Proof
"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.