1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Insights The Millennium Prize Problems: Part I - Comments

  1. Jan 7, 2016 #1

    kreil

    User Avatar
    Gold Member

    Last edited: Jan 8, 2016
  2. jcsd
  3. Jan 7, 2016 #2
    Great overview! PF can we solve these problems!? :)
     
  4. Jan 7, 2016 #3

    A. Neumaier

    User Avatar
    Science Advisor
    2016 Award

    I had tried my hands on problem 2, ##P=NP?##.

    After hard work, I was able to reduce the problem to the question of whether ##P=0## or ##N=1##.

    My most successful attempt to prove ##P=0## (which would have settled the conjecture in the affirmative) was by noting that for any ##X##, we have ##P(X-X)=PX-PX=0##. Thus after division by ##X-X##, we find that ##P=0##. Unfortunately, this argument proved to have a gap, since for the argument to work, the divisor must be nonzero. Thus I would have to find an ##X## such that ##X-X## is nonzero. Unfortunately again, I could prove that this is never the case. Thus I couldn't close the gap in my argument.

    I am sorry that I have to conclude that the problem is still open. )-:
     
    Last edited: Jan 7, 2016
  5. Jan 7, 2016 #4
  6. Jan 7, 2016 #5

    A. Neumaier

    User Avatar
    Science Advisor
    2016 Award

    Someone else had tried Problem 5, Yang-Mills Theory Existence and the Mass Gap. I spent a lot of time reviewing his papers (see also here). Unfortunately, the (in contrast to my previous post serious) result of my investigations was that the papers didn't satisfy the standards required by the official problem description.
     
  7. Jan 7, 2016 #6

    A. Neumaier

    User Avatar
    Science Advisor
    2016 Award

    You refer to a section on a Wikipedia page that talks about
    ''how to solve in a way that is faster than testing every possible answer''
    and paraphrase this in your own story.

    This is a very misleading way to popularize the problem. There are many NP-complete problems where there are plenty of techniques that solve the problem much faster than by testing every possible answer.

    An example where I know all the details is the linear integer feasibility problem, asking for deciding whether a system of linear inequalities with integral coefficients has an integral solution. Branch and bound (and enhancements) is the prototypical method for solving these problems, and fairly large problems can in many cases of practical interest be solved quickly. It is also known that the problem can always be solved in finite time. But testing each possible answer takes an infinite amount of time.

    Nevertheless, this has no effect on the validity of P=NP or its negation, which are effectively statements about the asymptotic worst time cost of a family of problems whose size grows beyond every bound.
     
  8. Jan 7, 2016 #7

    kreil

    User Avatar
    Gold Member

    @A. Neumaier, Thank you for the feedback, I will update that last paragraph on the P = NP problem to more accurately reflect the implications.
     
  9. Jan 8, 2016 #8

    Drakkith

    User Avatar

    Staff: Mentor

    Nice article! Now, who wants to help me solve pointy-whatsits conjecture?!
     
  10. Jan 8, 2016 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    It is FAR from true that only one of Hilberts problems remain unsolved....
     
  11. Jan 8, 2016 #10

    kreil

    User Avatar
    Gold Member

    Thank you @micromass, I updated the article accordingly.
     
  12. Jan 8, 2016 #11
    So that is 6 million if I solve them all, which is probably what it will wind up costing for me to build a "real-ly" quantum computer which could solve them all and many 21st century and beyond problems. Can anyone spare 6 mil for a few years? I'm sure the computer has the potential to be worth billions, as if "cost" and "worth" would still have any relation for very long.

    The world wouldn't change dramatically if these were all "solved" in of itself, would it?
    (Besides the countless hours numerous people won't spend trying to solve it!)
     
    Last edited: Jan 8, 2016
  13. Jan 8, 2016 #12

    klotza

    User Avatar
    Gold Member

    Good article, can't wait to read about the physics-related problems in part 2.
     
  14. Jan 9, 2016 #13

    A. Neumaier

    User Avatar
    Science Advisor
    2016 Award

    ''The ramifications of a solution to whether P=NP would be enormous.'' - only if solved in the affirmative. Proving ##P\ne NP## would have no practical implications at all. But it would revolutionize the proving techniques for lower bounds in complexity theory. Therefore I belive the problem will never be solved.
     
  15. Jan 11, 2016 #14

    Ssnow

    User Avatar
    Gold Member

    Nice presentation!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: The Millennium Prize Problems: Part I - Comments
  1. Millennium Problems (Replies: 11)

  2. The Millennium problems (Replies: 16)

Loading...