Starship Asterisk*

Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper titled simply "P ≠ NP".

This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute's seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.

The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P.

If the answer to a task can be checked quickly then it is in class NP.

So if P = NP, every problem that can be checked quickly can also be completed quickly. That outcome would have huge repercussions for internet security, where the difficulty of factorising very large numbers is the primary means by which our data is kept safe from hackers.
...
Complexity theorists have given a favourable reception to Deolalikar's draft paper, but when the final version is released in a week's time the process of checking it will intensify.

P is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.

Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work now—a task that could go on for a long time. If he’s correct, Deolalikar will have figured out one of the Clay Mathematics Institute’s seven Millennium Prize Problems, for which they give $1 million prizes. (Grigory Perelman won one of the seven for solving the Poincaré conjecture, but turned down the money last month.)

What’s all the hubbub? First, an explainer:

• The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P. If the answer to a task can be checked quickly then it is in class NP [New Scientist].

That definition is pretty abstract, so here’s a more concrete example:

• Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large — more than the total number of atoms in the universe — but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean’s prohibited pairs is on the list, that’s an error [AOL News].

Thus, if P were equal to NP, it would mean that problems that are easy to check—like this roommate match-up—must also be easy to solve. But if Deolalikar is correct and in fact P is not equal to NP, as many mathematicians already believed, then that ain’t necessarily so. And that would have practical meaning, according to Michael Sipser of MIT.

• Sipser … says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says [MIT News].

Deolalikar’s proof is now available to read online. New Scientist and Network World report that he pulled together tactics from different disciplines to show that an NP problem—whether a list of statements can be simultaneously correct or contradict one another—is not a P problem, because it can be easily checked but no computer can figure it out quickly from scratch.

In the days since the proof began to spread across the Internet, however, some math bloggers like Scott Aaronson have responded to the proof by saying yes, it’s lovely, but no, it probably isn’t going to stand.

http://en.wikipedia.org/wiki/P_%3D_NP_problem wrote:

Euler diagram for P, NP, NP-complete, and NP-hard set of problems

---

(Other) reasons to believe P ≠ NP

According to a poll many computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems. These algorithms were sought long before the concept of NP-completeness was even defined. Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.

It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience.

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...
— Scott Aaronson, MIT

On the other hand, some researchers believe that we are overconfident in P ≠ NP and should explore proofs of P = NP as well. For example, in 2002 these statements were made:

The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. [. . .] The resolution of Fermat's Last Theorem also shows that very simple questions may be settled only by very deep theories.
—Moshe Y. Vardi, Rice University

Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.
—Anil Nerode, Cornell University