Insights The Millennium Prize Problems: Part I - Comments

[kreil]

kreil submitted a new PF Insights post

The Millennium Prize Problems: Part I

Continue reading the Original PF Insights Post.

 

[Greg Bernhardt]

Great overview! PF can we solve these problems!? :)

 

[A. Neumaier]

PF can we solve these problems!? :)

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. )-:

 

[Greg Bernhardt]

@micromass let's do it!

 

[A. Neumaier]

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

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.

 

[A. Neumaier]

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.

 

[kreil]

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

 

[Drakkith]

Nice article! Now, who wants to help me solve pointy-whatsits conjecture?!

 

[micromass]

It is FAR from true that only one of Hilberts problems remain unsolved...

 

[kreil]

It is FAR from true that only one of Hilberts problems remain unsolved...

Thank you @micromass, I updated the article accordingly.

 

[jerromyjon]

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!)

 

[klotza]

Good article, can't wait to read about the physics-related problems in part 2.

 

[A. Neumaier]

''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 believe the problem will never be solved.

 

[Ssnow]

Nice presentation!