Insights The Millennium Prize Problems: Part I - Comments

1. Jan 7, 2016

kreil

Last edited: Jan 8, 2016
2. Jan 7, 2016

Greg Bernhardt

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

3. Jan 7, 2016

A. Neumaier

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
4. Jan 7, 2016

5. Jan 7, 2016

A. Neumaier

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.

6. Jan 7, 2016

A. Neumaier

''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.

7. Jan 7, 2016

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.

8. Jan 8, 2016

Staff: Mentor

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

9. Jan 8, 2016

micromass

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

10. Jan 8, 2016

kreil

Thank you @micromass, I updated the article accordingly.

11. Jan 8, 2016

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

Last edited: Jan 8, 2016
12. Jan 8, 2016

klotza

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

13. Jan 9, 2016

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

14. Jan 11, 2016

Ssnow

Nice presentation!