Slashdot Mirror
Wiki to Help Solve Millennium Problems?
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?"
3/4 of the people will argue about their misunderstanding of the problems involved, the other won't even know what the problems are but think they do. The very few people who actually do understand the problems and the underlying issues will eventually stop trying to explain what the real issue is.
Wiki to be created to solve Grand Unified Theory of Everything, this will take over because physicists, chemists, mathematicians have failed to do it, so the idea is to lob it out there. First step will be to resolve the problems between gravity and quantum mechanics.
Lets put it this way, if there was a Wiki on solving complex DNA evolution problems, 50%+ of the posts would be from wackos talking about ID and Creationism.
I hate to break it to people, but Maths and Physics make computing look like a liberal arts degree.
An Eye for an Eye will make the whole world blind - Gandhi
That's a simple one. The missing mass is vaporware from all the features that Microsoft was promising for Windows Vista and all the promises the Duke Nukem Forever will be released. Once Windows Vista is fully featured and Duke Nukem Forever is released, the equations should work correctly. The odds of that happening is... like a spaceship being swallowed by a large dog in space. :)
Keep in mind that there already is a kind of wiki-like "collaboration" within the academic circles. The only difference being that the circle is relatively small compared to a "wiki".
But then, more people working on it doesn't necessarily improve things. For one, you will expect a very bad noise to signal ratio, where there would be a bunch of smart ass ideas that have already been disproved decades ago, or ideas which are so obviously wrong that no academic would even think of writing a paper for.
Basically the whole thing is based on the assumption that "monkeys banging on typewriters will eventually produce all the works of shakespear". It works in theory, but remember that it takes either an infinite number of monkeys, or infinite time -- whereas you could find a group of talented people to do the same job more effectively.
Expect a dozen claims of "TSP solved in P time!" from this site within a month, and nothing more afterwards.
Don't quote me on this.
I think this is a great approach. Its effectiveness is questionable, but that is the story with everything else. Seems as though it should at least help shed some light on different approaches to some of the problems and maybe help those that are truly the 'professionals' that have been cranking on these problems to see some insight and fresh ideas. Kinda just rolls with the oss philosophy of having as many eyes and brains as possible looking at code to find the bugs and to provide creativity...so why not math. Maybe this will also open up more opportunity for those with gifts in programming to find methods to help design new methods for computational approaches to these problems. Will it cure cancer, stop hunger, prevent aids/hiv...no. But basic research is basic research, so why not.
my site of misleading and incorrect information!
The important difference there was that this project was only open to those actually actively involved in working on this problem. A public wiki will likely be bogged down by people who don't truly understand the problem or the approaches used to solve them - instead of everyone being able to contribute a little (as is possible in Wikipedia, which effectively just requires a transcription of information) the vast majority of people won't have anything to offer at all. And of course, those that are actively involved in working on these projects and want to share their work are in all likihood already doing so - with other people in the same field.
This project will likely attract those who do not have the particlar interest, time or background to work in a focused fashion on the problem, and consequently I'd be surprised if anything really unique or surprising came out of the project.
I'm a professional mathematician and I find the idea interesting.
Real researchers are familiar with cranks on newsgroups (James S Harris on sci.math for example) who year in year out claim to have proved this or that famous conjecture. Or, these people send proofs to real researchers, expecting attention when page one of their "proof" contains an error. So my hopes are not high that a community of semi-qualified people could solve the problems, but....
Suppose that this community set about collating and putting in context all of the material related to those problems that exists in the **research level** literature and **expounding** it in an extremely clear way. And suppose that real researchers were interested and joined the effort. This resource could be a HUGE contribution to the effort.
Unfortunately, the only joint efforts in mathematics on the web so far, do not deal seriously with the literature, but approach mathematics at a level of understanding of a first year graduate student. Problems that are well understood by the most brilliant minds on the planet are not going to be solved by people with an understanding as limited as that. It isn't as though some tough problems haven't been solved with elementary methods (the Kayal-Agrawal-Saxena result being a case in point), nor is it true that cranks do not occasionally come up with the goods (de Branges proof of the Bieberbach conjecture being a case in point), but the fact is, these are exceptions to the rule and the vast majority of difficult problems had immensely difficult solutions which took new developments in mathematics over periods of many years before they could be solved. Will a community of non-researchers make developments in modern mathematics? Personally I doubt it.
But, this is a new idea, hasn't been tried, so who knows where it will lead. As a research mathematician, the idea intrests me, and I would be involved if it headed in the right direction and didn't become a place for cranks to meet and fiddle with polynomials over an unspecified ring.
The real>/i> question is, will this Wiki be able to reach its solutions in non-Polynomial time?
A lot of people on Slashdot are degree-obsessed; at an early age they have bought into the idea that everybody who does not have a formal academic education to at least PhD level is necessarily unable to contribute anything to research. (This is not just the chip on my shoulder talking, but as someone with a degree from Fen Poly who has recruited a fair number of graduates over the years, I know it takes far more than a degree or two to make a scientist, mathematician or even a developer. Curiosity, persistence, the ability to see connections are all important.) Although this Wiki may well fail, it might just bring to light a few more Ramanujans. The world does not consist solely of North Americans, and there are doubtless plenty of educated people in other cultures who do not have access to the networks that bring some people to the fore while others, equally well endowed, may never get an opportunity.
Pining for the fjords
Speaking as someone with a Ph.D. in mathematics ...
...
These problems are all incredibly difficult. A lot of very good mathematicians have thought about them, in some cases for over a hundred years. In some cases, even understanding the problem requires an advanced mathematical education. If there was anything approaching an easy solution, it would have been found already. That said
Problems like these always require some insight. Typically, either a way to relate the problem to some other unexpected area, or some new kind of machinery that creates a leverage against the problem.
Personally, I wouldn't expect that from such an effort.
At first glance, I'm not sure HOW this is an "unsolvable" problem. Would I not just select and group 100 students at random then rearrange the pairs as I found incompatibilities? Can someone clue me in to what I'm missing here?
... * 1. Since we're trying every possible combination, this gives us:
7 66515247971418153526438677698477539372878051288400 0
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.
I remember when I was in high school and someone first explained the P=NP problem to me. This was certainly someone who was very smart. I remember he had made big bucks at Microsoft doing some sort of software work. He told me he was reading a book about the problem (I'm not sure which one, there are many), and was going to "work on it". He told me about the millenium prize competition. But he said something else that really underlined for me the disconnect between Academia and the business world:
He told me that if he he solved the problem by showing P=NP (instead of P!=NP, which "most mathematicians believe"), he wouldn't publish his proof. Instead, he would setup a website that would take credit card payments to solve problems quickly (for example, packing boxes into the back of a UPS truck, or various traveling salesman problems). At the time, I though this was a little antisocial, but not much more.
Later, when I had more mathematical training, I looked back on this and realized how revealing this attitude was: of course, if someone proves P=NP, the proof will almost certainly not be accompanied by practical algorithms which are significantly better than those used already for problems on most scales. Of course, the idea that he was going to solve this problem without any collaboration or formal education in logic or complexity theory demonstrated the arrogance typical of many super-successful business-people. I can't help but remark that for all the stupid patents on software "ideas" and sometimes algorithms, we're lucky that, most of the time, theoretical advances are made not by people like this... and and so people publish their results, and are rewarded with respect rather than dollars.
Imagine the state of our theoretical knowledge in mathematics and computer science if, even in Academia, every discovery of a new algorithm or idea resulted in a patent application, and was jealously guarded as a secret which could produce profit. Unfortunately, this is already largely the state of things in the wet sciences (unnecessarily so, I would argue, and point to mathematics as my evidence).
As for the wiki thing: I don't think most ordinary people are like this guy, so hey, good for the wiki. (I think this attitude is taught by the business world, and not somehow the other way around). Unfortunately, I fear that the millenium problems are deep enough that amateurs will have trouble making a big impact. There are a few amateur contributions to mathematics occasionally, but there hasn't been a significant one in a long time. (The last was arguably by Marjorie Rice, a housewife who essentially resolved the question of the number of different ways to tile the plane with convex pentagons). Astronomy is probably the last big field where amateurs play a really significant role.