P=NP?

[sec_ware]

Hi

The first impact would be that Clay[1] may have to pay one million $
...so there always will be rumors (any references?).

Second, lot's of people, among them genuine researches, claim to
have found a P solution to an NP problem. One of the more serious
ones was a paper by Plotnikov[2]. Still, the challenge is open.

Third, have a look at the wikipedia-article[3]. There are listed a couple
of consequences.

Fourth, we may not need quantum computers anymore

And fifth, almost any computational research team may profit
of such a discovery, if the solution may be applicable to their
own problem. This is crucial: in order to solve the NP problem
you need an algorithm that does not cut down one particular
NP problem, but all of them (bounded runtime by a polynomial).

In physics, for example, when you study computationally
problems involving fermions, there is a famous "fermion sign problem"[4]:
the physical signal vanishes exponentially, while the error remains
constant. Thus, available algorithms need exponential runtime.
A reduction to a polynomial time would be fantastic.


Cheers

/edit (thanks dinowuff: link corrected "vol1" -> "Vol1" while looking for a mirror, I found this page[5], which summarizes the milestones since ~1986.


[1] http://www.claymath.org/millennium/P_vs_NP/
[2] http://www.emis.de/journals/SWJPAM/V...6/plotnikov.ps
[3] http://en.wikipedia.org/wiki/P_%3D_NP_problem
[4] http://militzer.gl.ciw.edu/diss/node25.html
[5] http://www.win.tue.nl/~gwoegi/P-versus-NP.htm