Hard Light Productions Forums
Off-Topic Discussion => Programming => Topic started by: blackhole on August 08, 2010, 09:20:13 pm
-
A paper has been published proving that P != NP.
http://www.scribd.com/doc/35539144/pnp12pt (http://www.scribd.com/doc/35539144/pnp12pt)
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.
http://en.wikipedia.org/wiki/P_versus_NP_problem (http://"http://en.wikipedia.org/wiki/P_versus_NP_problem)
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.
-
Wow, that's amazing. I never thought this would get done in my...
...well I was planning to live for thirty thousand years, but at least not in my FIRST lifetime!
-
Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine.
I guess they found the eggbeater! :D
-
The bad news is that one of these pops up every few years, without success so far. Of course, this time may be different... you never know. :p Not holding out any serious hope in this corner, though.
-
It would be a huge development in math and computer science if this has been solved. It will take years for people to fully check the paper though, and as Sushi said, all of these famous problems have had numerous false attempts at them, even from credible and well known researchers.
Although it's not exactly true that NP problems cannot be "solved efficiently." There are many cases of problems that are NP but still have approximate or probabilistic methods that work well in practice.
-
Well, it's already looking like the paper has some errors from what I'm reading on math blogs, and the author seems to have removed it from his website. :p It remains to be seen whether they can be fixed. Even if they cannot be though, these failed attempts at such problems still often have good insights and bring new ideas to the table.
-
The author has published the third draft (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf) of the paper.
If it holds up, it kind of disappoints me. P == NP seemed a much more interesting result.