P=NP?
Results 1 to 7 of 7

Thread: P=NP?

Hybrid View

  1. #1

    Exclamation 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?

  2. #2
    Senior Member
    Join Date
    Mar 2004
    Posts
    557
    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)

  3. #3

    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.

  4. #4
    Senior Member
    Join Date
    Mar 2004
    Posts
    557
    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)

  5. #5
    THE Bastard Sys***** dinowuff's Avatar
    Join Date
    Jun 2003
    Location
    Third planet from the Sun
    Posts
    1,250
    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:5B8:41:56:C5:63:56:88:C0

  6. #6
    THE Bastard Sys***** dinowuff's Avatar
    Join Date
    Jun 2003
    Location
    Third planet from the Sun
    Posts
    1,250
    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:5B8:41:56:C5:63:56:88:C0

  7. #7
    They call me the Hunted foxyloxley's Avatar
    Join Date
    Nov 2003
    Location
    3rd Rock from Sun
    Posts
    2,528
    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.
    55 - I'm fiftyfeckinfive and STILL no wiser,
    OLDER yes
    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
  •