Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The P vs. NP millennial prize problem

  1. Oct 1, 2014 #1
    Question: Does anyone know what the Millennial Institute's standards are to consider the P vs. NP problem solved?

    Namely, if one were to find a solution to the particular problem of subset sums in polynomial time, but one didn't know how this solution could be mapped onto other NP-complete problems, would the Institute consider the problem solved, since presumably (though I'm not sure if this is true) a polynomial solution to any NP-complete problem can be translated into a polynomial solution to all the others?

    What I mean is: if I knew enough about number theory and combinatorics to prove that the subset sum problem can be solved in a polynomial number of steps, but didn't know jack about computation theory or algorithms, would that suffice? Or would I have to master and include the algorithmic language necessary in a submitted paper for the Institute to even take me seriously?

    Or is it even possible for there to be a solution to one NP-complete problem that is not translatable to the others?
  2. jcsd
  3. Oct 2, 2014 #2
    No. A problem is only np-complete if every other problem that is in np can be reduced to it in polynomial time.
    To show this you only have to show that one other problem known to be np-complete can be reduced to your problem in polynomial time.
    I'm sure a reference to a proof would be sufficient.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: The P vs. NP millennial prize problem
  1. Problems in NP (Replies: 5)

  2. Skill vs. Luck Problem (Replies: 1)

  3. P vs NP and factoring (Replies: 3)