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?
Printable View
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: