-
January 29th, 2008, 10:26 PM
#1
Junior Member
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?
-
January 29th, 2008, 10:59 PM
#2
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
Last edited by sec_ware; January 30th, 2008 at 11:31 PM.
If the only tool you have is a hammer, you tend to see every problem as a nail.
(Abraham Maslow, Psychologist, 1908-70)
-
January 29th, 2008, 11:25 PM
#3
Junior Member
The Truth
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.
-
January 30th, 2008, 08:29 AM
#4
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
If the only tool you have is a hammer, you tend to see every problem as a nail.
(Abraham Maslow, Psychologist, 1908-70)
-
January 30th, 2008, 08:34 PM
#5
Yo Sec
http://www.emis.de/journals/SWJPAM/v...6/plotnikov.ps gives me a 404.
Do you have another link to the paper?
09:F9:11:02:9D:74:E3:5B 8:41:56:C5:63:56:88:C0
-
January 31st, 2008, 02:39 PM
#6
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!
09:F9:11:02:9D:74:E3:5B 8:41:56:C5:63:56:88:C0
-
January 31st, 2008, 02:59 PM
#7
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
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
Last edited by foxyloxley; January 31st, 2008 at 03:04 PM.
so now I'm in my SIXTIES FFS
WTAF, how did that happen, so no more alterations to the sig, it will remain as is now
Beware of Geeks bearing GIF's
come and waste the day :P at The Taz Zone
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
|