P=NP?

There are rumors that the Traveling Salesman problem has been reduced to P. How would you react if P=NP? How will you respond to this cryptology threat? Does anyone know what would happen if the Riemann Hypothesis proved to be false?

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

The Riemann Hypothesis is false and P=NP. I never publish this due to the fact I am a creationist and consider the “separation of church and state” meaning my research is irrelevant. I am willing to give you a prime that is off the critical line to prove this is true. I just want to see whether the scientific community could accept it.

Hi

Andrew Wiles[1] proved a while ago Fermat's last theorem.
For this so seemingly simple statement[2], another deep
mathematical conjecture (Taniyama–Shimura conjecture,
which is about elliptic curves and thus, to some extent,
also relevant as a basis for some part of cryptography.)
had to be proven. He presented his proof in a three day
session in front of renowned mathematicians - and was
accepted.

Research actually should be the search for the truth - obviously,
there are some human beings who want to define the truth and may
misuse their status - be it a famous researcher, a creationists, whatever.
The scientific community can accept everything, as long as it is
proven in a scientific way (it should resemble Aristotle's logic).

...what a useless post...


Cheers

[1] http://video.google.com/videoplay?do...28330690408516
[2] http://en.wikipedia.org/wiki/Fermat's_last_theorem

Yo Sec

http://www.emis.de/journals/SWJPAM/v...6/plotnikov.ps gives me a 404.

Do you have another link to the paper?

sec_ware:

You must spread some Reputation around before giving it to sec_ware again.

Thanks so much for the updated link. And the summary paper is a VERY nice find.

As we say here in the Midwest. YOU ROCK!

aye, a very good read,I have the book by Simon Singh, read it years back, still can't get my head around all the details :p
but it makes for an entertaining read
nice post Sec~ cheers

and Overlord~ read sec's post, then look at yours !!!!
if you could have added some details / background / your reason of interest / LINKS / make it more interesting

jeez, here for years, and still only posting like a juvenille
the thread picked up after a decent reply

if you had added the details I suggested, it would have attracted a lot more attention, generating a far better discussion on what is actually quite an important mathamatical quest

my 0.02c
jeez but I ramble on :eek: