Slashdot Mirror

No, you don't need to. But if you say just the right things, you will have earned one million dollars. And believe me, you will have earned it...

But coming back to reality, I don't think too many people really assume that "P=NP". Then again, there's really no argument yet to prove those who do wrong.

So yes, I recant. You do need to say more... it might after all turn out that the formal definitions of P, NP are such that P=NP, meanwhile having nothing to do with "real world" computation. This non-answer itself would be very interesting!

Worse, what happens if the formal definitions of P, NP are such that "P?NP" is undecidable?...

Hilbert's problem #6, asking for a proof of the Riemann conjecture, will now get you a $1 million prize if you can solve it. Good luck, people have only been trying for 140 years.

However, try and think about what this problem really is mathematically, rather than in terms of chess or magic squares. A knight's tour requires the knight to visit every square on the board exactly once. Replace "squares" with "nodes," and "board" with "graph," and what we have here is the problem of finding a Hamiltonian path with some interesting constraints.

And that's where this problem gets interesting- finding a Hamiltonian path on a graph is known to be NP-complete, a designation which carries with it all sorts of baggage, including some of the million-dollar sort. The fact that the question of whether magic knight's tours exist on an standard 8x8 board required 60+ CPU-days to answer speaks volumes about the complexity of the problem, and demands answers as to how this complexity comes about, and why there is no solution with the given constraints. Far from being just a silly mathematical curiosity, this is a problem that presents a lot of potential applications with regards to algorithms, complexity, and computability. Also, if you can find an algorithm that finds Hamiltonian paths in polynomial time, you get the aforementioned free money.

So yes, the problem of finding a magic tour seems worthless if you only consider the problem literally in terms of a chessboard and magic squares, instead of as a model for other complex problems in mathematics, science, and engineering. But by the same token, how interesting and useful would the Traveling Salesman Problem be if it were only applied to traveling salesmen?

However, try and think about what this problem really is mathematically, rather than in terms of chess or magic squares. A knight's tour requires the knight to visit every square on the board exactly once. Replace "squares" with "nodes," and "board" with "graph," and what we have here is the problem of finding a Hamiltonian path with some interesting constraints.

And that's where this problem gets interesting- finding a Hamiltonian path on a graph is known to be NP-complete, a designation which carries with it all sorts of baggage, including some of the million-dollar sort. The fact that the question of whether magic knight's tours exist on an standard 8x8 board required 60+ CPU-days to answer speaks volumes about the complexity of the problem, and demands answers as to how this complexity comes about, and why there is no solution with the given constraints. Far from being just a silly mathematical curiosity, this is a problem that presents a lot of potential applications with regards to algorithms, complexity, and computability. Also, if you can find an algorithm that finds Hamiltonian paths in polynomial time, you get the aforementioned free money.

So yes, the problem of finding a magic tour seems worthless if you only consider the problem literally in terms of a chessboard and magic squares, instead of as a model for other complex problems in mathematics, science, and engineering. But by the same token, how interesting and useful would the Traveling Salesman Problem be if it were only applied to traveling salesmen?

If we stretch a rubber band around the surface of an apple, then we can shrink it down to a point by moving it slowly, without tearing it and without allowing it to leave the surface. On the other hand, if we imagine that the same rubber band has somehow been stretched in the appropriate direction around a doughnut, then there is no way of shrinking it to a point without breaking either the rubber band or the doughnut. We say the surface of the apple is "simply connected," but that the surface of the doughnut is not. Poincaré, almost a hundred years ago, knew that a two dimensional sphere is essentially characterized by this property of simple connectivity, and asked the corresponding question for the three dimensional sphere (the set of points in four dimensional space at unit distance from the origin). This question turned out to be extraordinarily difficult, and mathematicians have been struggling with it ever since.

If by "current, state-of-the-art" you mean Public Key techniques, of which the only unbroken ones known are factoring (RSA) and discrete log (Diffie-Hellman), then yes, quantum computing will break these. Public Key needs an easy problem that has a hard inverse, such as testing for primality and factoring. Factoring is hard now, but is easy with a quantum computer. Whether there is an appropriate problem with quantum computing available is unknown. You may have heard of the big debate on P=NP? NP contains P. QP, the set of problems solvable by a quantum computer in polynomial time, is in the middle. NP contains QP and QP contains P. Quantum computing does not break private key methods such as DES and AES.

I see two prospects for quantum computing. We may discover there is some natural limit which makes impossible the construction of a quantum computer with enough quantum bits to be useful. I think the chances of that are low. Or we'll have a working quantum computer before too long. Just when is the question. 5 years? 10? 50? Who knows? But if we look at history, we've got examples which may apply. The transistor was invented in 1948, the IC in the 1960's and personal computers by the late 1970's. Based on that, 30 years for usable, affordable quantum computing to get to the masses seems reasonable. Except I would shorten that because the world is larger (more population) today.

I read the article and understood most of what they were talking about...but I knew I had heard something related to this before.

The Poincare Conjecture

IIRC, solving this problem should make some major advances in this 'tube-theory'. Can anyone explain how though?

---

Can be found here

Perhaps you are wondering what an NP-complete problem is or what this P vs. NP stuff is all about. You might want to check out the comp.theory FAQ and scroll down to 7. P vs NP. It gives a bit of history and a decent description.

Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.

Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling [nada.kth.se] to multiprocessor scheduling.

Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)

Perhaps you are wondering what an NP-complete problem is or what this P vs. NP stuff is all about. You might want to check out the comp.theory FAQ and scroll down to 7. P vs NP. It gives a bit of history and a decent description.

Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.

Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling [nada.kth.se] to multiprocessor scheduling.

Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)

Unfortunately the money may take a while in coming. The rules state, "a proposed solution must be published in a refereed mathematics journal of world wide repute, and it must also have have general acceptance in the mathematics community two years after." After this a committe is formed to determine whether the money should be awarded.

This problem is priced at $1 million if solved.

well ERH is a million dollar problem (literally) !! Claymath.org, so i wouldn't bet my money on a proof which relies on ERH.

Thanks. Great explanation.

Very kind of you to say, thanks.

Could you elaborate and tie this in with the number of primes between m and n?

I'm a little less confident about this, but here goes...

As I understand it (and bear in mind that I've not done any complex analysis for several years, and number theory has never really been my forte) sometime during the 19th century Gauss noticed that the distribution of primes was approximated pretty well by a function he called the `logarithmic integral'.

Li(x) is defined as the integral from 0 to x of (1/t) dt. And apparently the number of primes below x (usually denoted pi(x)) is pretty well approximated by Li(x).

Now this is where I start to lose track of things.
As I understand it, it was proved at the beginning of the 20th century that the validity of the Riemann hypothesis is equivalent to the assertion that the deviation of Li(x) from the actual value of pi(x) is of the order of sqrt(x)*ln(x).

If I remember correctly, some work of the three great British mathematicians Hardy, Littlewood, and Hardy-Littlewood showed that pi(x) actually oscillates around Li(x) infinitely many times (although it really doesn't do it very quickly - the first value of x for which the graphs cross is very big indeed).

qv: the Clay Institute's page
and Chris Caldwell's page for better explanations.

As to whether there's a relatively simple proof out there, I don't know. My (non-specialist) suspicion is that there isn't, because some really clever people have tried to find one for a century and a half and failed. I'd be interested and impressed to be proved wrong on this, though.

Andrew Wiles' celebrated proof of Fermat's Last Theorem (if you haven't done so, read Simon Singh's book on the subject, and if possible watch the BBC Horizon documentary - the transcript is available) was pretty complicated and, I'm told (algebraic geometry isn't my field either - there's an awful lot of diverse mathematics out there) introduced some genuinely new ideas and methods.

The general feeling is that if there were a simple proof of either Fermat or Riemann (or, for that matter, the Goldbach or Poincare Conjectures) then someone would have found it by now - some really top brains have worked on all of these over the years (including several Fields medallists, FRSes, and the like).

(There's a guy who posts regularly to sci.math who reckons he's got a simple proof of Fermat which doesn't resort to all that scary stuff about elliptic curves or modular forms. The consensus seems to be that he's a nutter, though - his `proofs' contain obvious flaws which he refuses to acknowledge, claiming instead the existence of an enormous academic conspiracy against his work.)

It's also often the case (and this was true for the Fermat theorem) that proofs of such intractible problems, even those which are subtly flawed, introduce new ideas and methods of attack.

This is why otherwise sensible mathematicians have a go at these problems - even if they don't manage to solve them, the chances are that the attempt will inspire them to find new methods or potentially important partial results. Even had Wiles' original (flawed) proof turned out to be irrepairable, it was a pretty major piece of work which introduced some important new ideas which could well be useful in solving related problems.

My guess (as an interested non-specialist) is that while a proof of RH would be complicated and elegant, it would also involve some new twist or idea. As for who might do it, my money would be on Prof Louis de Branges of Purdue University - he demolished the (similarly intractible) Bieberbach Conjecture in the 1980s and thus seems to know what he's doing. Or it might be someone else entirely, someone who's spent seven years locked in their attic (as Wiles did).

nicholas

no shit?

think it might be because differential equations are about a million times harder?

the problem is that mathematicians devoted their lives to the study of differential equations, and there's tons of unsolved problems problems. calculus is pretty much trivial.

i'll bet you a million dollars that differential equations are hard

These lists, although quite influential, are not quite like a "distributed computing" idea. These are just big open questions sitting out there. They're really hard to solve. Now, one could imagine that someone posts on usch a server saying, i think we can parse this certain problem into the following 15 pieces, and then people can solve this. This is exactly what one does with their advisor when working on a PhD thesis, for example. Such a system would bring the problems closer to the forefront, so to speak.

You show great skill at cut & pasting from http://www.claymath.org/prizeproblems/poincare.htm : )

Just kidding. Go ahead, enjoy the cut & paste karma.

Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.

Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling to multiprocessor scheduling.

Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)

Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.

Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling to multiprocessor scheduling.

Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)

Clay Math Institute in Cambridge has a bunch of stuff on P vs. NP. Here is the link to their site about it. Proving (or disproving) this one gets you a million bucks.

Wow, this is such great timing. I've been studying for my computability final for next tuesday and this was the topic that I didn't really get...

Anyways..just as a note, NP doesn't not mean O(NP) as many of you are talking about. O(n) is a term for speed of an algorithm. P vs NP problems deal with whether something is calculatable

If anyone has some free time and wants to win a million dollars read this: The P versus NP Problem (oh..did I forget to mention that you must be a genius in computablity) Here is the press release about the $1 million prize money.

Wow, this is such great timing. I've been studying for my computability final for next tuesday and this was the topic that I didn't really get...

Anyways..just as a note, NP doesn't not mean O(NP) as many of you are talking about. O(n) is a term for speed of an algorithm. P vs NP problems deal with whether something is calculatable

If anyone has some free time and wants to win a million dollars read this: The P versus NP Problem (oh..did I forget to mention that you must be a genius in computablity) Here is the press release about the $1 million prize money.

Wroot

Before anyone puts much time into this questionable effort ask Alex one question, "Where is the money?"

Maybe he's for real, I hope so, but most of these PRIZES either come from a well known philanthropist or foundation, or are the announcement of a fund to distribute money under certain conditions. For example the Clay Mathematics Institute in announcing their Milennium Prize for unsolved math problems stated The Board of Directors of CMI have designated a $7 million prize fund for the solution to these problems.

A number of you've been checking this guy out. Has anyone found the money yet?

There's actually a million dollar prize for solving that one. I guess if you solve it the right way you should be able to quickly claim your 1.6 mil.

1. People read the articles before posting.
2. Slashdot editors turned 30 seconds of their time toward making sure people can read the articles.

1. People read the articles before posting.
2. Slashdot editors turned 30 seconds of their time toward making sure people can read the articles.

There is a million dollar prize for proving the Riemann Hypothesis. See the Clay Institute Page.

to the Millennium Prize Problems page
to Ian Stewart's article on the problem.
to Stephen Cook's mathematical description of the problem (in .pdf format)
to Richard Kaye's Minesweeper Page

to the Millennium Prize Problems page
to Ian Stewart's article on the problem.
to Stephen Cook's mathematical description of the problem (in .pdf format)
to Richard Kaye's Minesweeper Page

to the Millennium Prize Problems page
to Ian Stewart's article on the problem.
to Stephen Cook's mathematical description of the problem (in .pdf format)
to Richard Kaye's Minesweeper Page

More details of the maths involved can be found at The ClayMath Institute's webpage and some related papers at R.W.Kaye's webpage

A much more detailed story is found at The Clay Mathematics Institute Website

Yes, this is in fact one of the seven $1,000,000 Millenium Prize Problems. The other six are The Hodge Conjecture, The Poincaré Conjecture, The Riemann Hypothesis, Yang-Mills Existence and Mass Gap, Navier-Stokes Existence and Smoothness, and The Birch and Swinnerton-Dyer Conjecture. More information is available at Claymath's website. It includes simple examples of the problems as well as lengthy PDF files explaining them mathematically.

You might also find the solution to this problem in Concrete Mathematics, a book of Discrete Mathematics. It is written in one of the side notes there that N=1 implies that P=NP. =-)

By the way, there is now $1,000,000 prize available for proving that P is or is not equal to NP. Of course, this could produce more correct, well-intentioned but wrong, and nutty solutions.

I would have, but that question was already covered in the aforementioned article

Heh heh...

http://www.claymath.org/prize_pr oblems/p_vs_np.htm

Methinks you slightly misinterpret the intended meaning. Innovation still exists - but if the "hot topics" at a university are basic problems of computer science, that have been studied and dissected for decades... well, I'm not going to expect the invention of the microchip.

Was ENIAC an innovation? Sure! So was Babbage's machine, and the vacuumn tube, and the transistor, and the IC, and the 8088. Is it innovation to add on-chip L2 chache? No - it's refinement of existing principles and concepts.

As for the value of a solution to Travelling Salesman - why, yes, that would be nice. Given the fact that these are classical examples of non-polynomial solution sets, I'd be more inclined to predict a solution from the mathematicians of the world (Slashdot, May 25, Mathematical Problems For The New Age, Is P=NP?)

Innovation means more than Micro$oft's tagline. It's something NEW, for which uses have to be invented (see the computer), or a completely new way to do something (see the integrated circuit). What's innovative software? Like p0rn, I'll know it when I see it.

Although it's interesting to see an academic body offer a lot of cash to solve these problems, they're asking the wrong crowd.

I'm certainly not qualified enough even to try to solve any of these, but I always found those unresolved problems quite interesting, and it's refreshing to see this article on /., among the huge amount of political one!

- Stephan.