Wiki to Help Solve Millennium Problems? 232
MattWhitworth writes "A new wiki has been set up over at QEDen to try to gather a community to solve the Millennium Problems. The problems are seven as yet unsolved mathematical problems that continue to vex researchers today. What do you think of this effort? Will gathering a community of people help solve problems such as P=NP, or do you think it requires a lot more than a semi-qualified community to approach the problem?"
Re:Please. . . (Score:2, Informative)
A scientist's work needs to touch on reality at some point. If a scientist doesn't understand why he's doing what he's doing clearly enough to tell an eight year old, then he's lost touch with the purpose of research. Even pure scientific research is explicable. "I'm trying to find out how quickly certain bits of the stuff we're made of stick to each other." At least, that's Vonnegut's contention there. An eight year old won't ask "Why are you spending my tax dollars on this?" so a simple answer will do.
Mathematicians have no such fallback. When studying fourier transformations or the normality of a decimal expansion, the concepts involved touch on our experience nowhere. You could stretch a point and pretend that the point of your fourier research is to fit more songs on her ipod, but you're probably lying there. Some fourier research did that, but yours won't necessarily result in better compression... and that's not actually what you're trying to do. You're no engineer.
Even though I majored in Pure Mathematics, I'm aware that there are mathematicians doing work the very existence of which I'm not educated enough to understand. Any very specialized branch of mathematics forms its own little universe. A very advanced mathematician, asked about his work, will say "You know about the existence of Tupper manifolds? Well it turns out that if their order is prime, they're non-haussman. I'm trying to figure out if non-tupper manifolds are all hausmann or not." (That's all made up, of course.)
Scientists may use mathematics, but science and mathematics are very different fields.
Re:solid approach (Score:5, Informative)
This is going to become an instructional site to teach people (hopefully correctly) what is going on in these fields, nothing more.
Online Encyclopedia of Integer Sequences (Score:3, Informative)
With over 100,000 web pages, searchable, with posters' email addresses given, and both internal and external hotlinks and citations to hardcopy literature, this has been the leading collaborationware in Mathematics. The Online Encyclopedia of Integer Sequences (or OEIS) recently faced a problem with increasing numbers of clueless postings.
The distinguished panel of editors, under Dr. Neil J. A. Sloane, first added a keyword of "probation." Submissions so tagged, unless okayed by an editor, are deleted after a reasonable time. At my urging, citing the history of Slashdot, they even more recently adopted the keyword "less" -- meaning less than interesting, but better than probation. "Less" sequences stay in the database, but are given minimum priority in searches.
Similarly, MathWorld [wolfram.com] is a form of collaborationware or pseudowiki. Although edited by Dr. Eric W. Weisstein and his staff, it encourages submission by form from anyone, and posts attribution to such submissions, and lists of contributors.
I contend that web-based systems have substantially affected the practice of Mathematics. Social mechanisms such as pioneered by Slashdot contribute to weeding out useless from interesting contributions. As with Wikipedia, one's academic credentials mean nothing here. What matters is the quality of one's submissions, as evaluated by one's online peers.
There also many fine Math blogs, but that's another topic.
-- Jonathan Vos Post [livejournal.com]
Re:P vs NP Question (Score:5, Informative)
What makes a problem NP is not whether it's solvable but rather how long it takes to solve. The algorithm you propose is a search algorithm. Consider what would happen if your list of incompatible students was so large that within the group of 100 students you randomly choose, there is not a single possible arrangement of pairs. This means you would have to choose another group of 100 students. It's a minor refinement but an important one.
Now consider if that list was so large that there was only a single possible group of 100 that contains an arrangement of pairs that worked. Now consider that within that group of 100, there was only one good possible arrangement. If you're very unlucky, and you choose these set of 100 and arrangement of pairs last, you have to try every possible combination before finding the right one. Okay, so what?
Lets see how many possible answers you'd have to try. Within a group of 100 students, there are 100 choose 2 possible arrangements. There are 400 choose 100 possible choices of 100 students. n choose k is really n! / (k! (n-k)!) where n! is n * (n - 1) *
[400! / (100! 300!)] * [100! / (2! 98!)]
Your standard calculator is not going to be able to solve this one but if you have an arbitrary precision calculator (like bc), you get:
1109718121819397093151989141664840784648478532850
Which is an awfully large number. That number is so large, in fact, that even if you have a computer that could check one possible solution with every electron in the universe, until the Sun supernova's, you'd still not find the answer.
Now, that depends on really bad luck. You can construct problems though that given average luck, you would not find the solution in the lifetime of the universe. This is what cryptography is based on.
Compare this to a standard sorting algorithm. To sort the list [3, 4, 5, 6, 7, 8, 9, 2, 1, 0] given a crappy algorithm like bubble sort requires n*n = 100 computations. You can solve this problem the same way using search though. You merely have to randomly arrange the list in every possible way and check to see if your random arrangement is sorted. There are n! possible arrangements of a list of n elements so there are 10! = 3628800 possible answers to search. You can see that even a crappy algorithm like bubble sort is much better than search.
The difference is even greater with larger lists. A problem that is only solvable via search is considered NP. A problem that is solvable with an algorithm in polynomial time (n*n is a polynomial) is considered P. The N in NP stands for non-polynomial.
So the problem here is whether there exists a polynomial solution for these set of problems that we've labelled NP. What makes this even more significant is that it has been proven that if we find a polynomial solution for one NP problem, we can create solutions for any NP problem. A lot is riding on the lack of existence of a polynomail solution for NP problems. If someone where to prove that there are indeed polynomial solutions to NP problems it would be earth-shattering. After the initial shock, it would also open up a whole new world of mathematics since a lot of things we didn't think were possible to do efficiently became possible.
Re:Feces (Score:2, Informative)
And the slashdot story [slashdot.org].
Informal definition of NP (Score:2, Informative)
Please do not contact the Clay Institute Directly (Score:2, Informative)
If someone claims to have a solution to ALL 7 problems - Drink!
If someone claims that P vs NP is an Algebra problem or tries to factor P out of NP - Drink!
If someone claims that they need notarized assurances that the Clay Institute is prestigious enough for THEIR solution - Drink!
If someone claims that they need time on the Institute Supercomputer because solving one of the Millennium Problems is part of their Mission, A Mission From God - CHUG!
If you are at all serious about your solution to these problems, you will pursue them in a better manner then trying to find back channel entry into academia. You can start by actually getting a degree in Mathematics and learning that the Maths community already has ways and means to consider and judge any solution you think you have. Trust me on this one, I've seen the underside to their tables.
Unruhe