August 8, 2010

P != NP

A paper has been published proving that P != NP.

So far, peer review has confirmed this finding and no errors have been found. This paper answers a question that has been called the most important question in the field of computer science.

P != NP has long been suspected by the majority of computer scientists, due to the fact that no polynomial time algorithms have been discovered for more then 3000 known NP complete problems. The consequences of proving either answer are explained in the paper's introduction:

Later, Karp [Kar72] showed that twenty-one well known combinatorial problems, which include TRAVELLING SALESMAN, CLIQUE, and HAMILTONIAN CIRCUIT, were also NP-complete. In subsequent years, many problems central to diverse areas of application were shown to beNP-complete (see [GJ79] for a list). If P!=NP, we could never solve these problems efficiently. If, on the other hand P=NP, the consequences would be even more stunning, since every one of these problems would have a polynomial time solution. The implications of this on applications such as cryptography, and on the general philosophical question of whether human creativity can be automated, would be profound.

If this paper continues to stand up to peer scrutiny and is declared a valid answer to the P vs. NP problem, this could very well mark a major historic moment in computer science and mathematics.

No comments:

Post a Comment