I sure could use a million dollars, what about you? Transitioning from Riemann's to P vs NP...

Many of the greatest problems are solved by an unknown individual. With this single concept in mind I've worked off and on trying out my skills at the Riemann Hypothesis... Getting nowhere fast, if anywhere at all. Having an understanding of the problem and the skills to investigate the work done by others is fairly rewarding and interesting. The problem actually provides a fairly high bar for those that might be interested in lending a hand. So forget it, been there done that, on to another million dollar problem.

Turns out the P vs NP issue might be a bit easier for the computationally minded. In fact it is warranted as the single most understandable millenium problem for the uninitiated. With that in mind it is also touted as the problem most likely to be solved first. Whether or not that is still the case as most of the research thrives around a couple of the core problems, I'm not sure. They may just fall first by pure brute force. Anyway, I check the Clay Institute website since every now and then you find a good link or two http://www.claymath.org/millennium/P_vs_NP/.

I have never really considered touching the P vs NP problem, but now I think it might be interesting. Seems back in 2000 Richard Kaye published a paper on the NP-completeness of Minesweeper. You can find out about that here http://www.claymath.org/Popular_Lectures/Minesweeper/. Even more fun, I think, is that he devises the proof that Minesweeper is NP complete by demonstrating the SAT problem can be rewritten in terms of Minesweeper diagrams. Some of them are pretty crazy, so you'll have to check them out, especially the AND gate and a number of the crossover diagrams.

Interested in why I'm bringing this up? Well, that travelling salesman problem is also NP complete and that means that optimal solutions to Squirrel .NET are also NP complete and for non arbitrary cases require an NP complete algorithm and can't be completed in P time. If you want a chance at a 1 million dollar prize you should head back a few posts (quite a few actually, I type a lot), and maybe give Squirrel .NET a few tries and then drop me an email to give you some harder versions of the puzzle.

Published Saturday, October 23, 2004 8:15 PM by Justin Rogers
Filed under:

Comments

Sunday, October 24, 2004 4:14 PM by haacked@yahoo.com (haacked)

# RE: I sure could use a million dollars, what about you? Transitioning from Riemann's to P vs NP...

I have an elegant proof of this that I wrote in the margins of my notebook... Oh. The dog tore it up.
Sunday, October 24, 2004 8:42 PM by Justin Rogers

# re: I sure could use a million dollars, what about you? Transitioning from Riemann's to P vs NP...

Whether your comment is in wit or jest is something left to the engaging mind. However, the implied allusion to Fermat in regards to the proof of his "last" theorem is somewhat ingenious in this context.

To note, Fermat's Enigma, a very small and highly achievable book for those of mathematical or non-mathematical mind alike, covers the history, if not the actual work, very well.
Sunday, October 24, 2004 9:39 PM by Justin Rogers

# re: I sure could use a million dollars, what about you? Transitioning from Riemann's to P vs NP...

De Brange has also demonstrated a previous attempt at the proof that wasn't successful. His current attempts may yet prove fruitful though. I'm not aware if he has of yet published his proof in an actual mathematical journal, nor have I seen very many individuals line up to examine/protect the proof as valid.

If you have more of a link than a public news site that would be great. His full paper is available online and several portions of the proof are less than accessible to my own inspection. Which is actually one of the reasons I started to switch off the problem, giving me a chance to study in some of the areas that I'm unfamiliar with in relation to this latest *proof*.
Tuesday, October 26, 2004 6:18 PM by Haacked

# re: I sure could use a million dollars, what about you? Transitioning from Riemann's to P vs NP...

It was an attempt at wit. I was once an aspiring mathematician (Majored in it). Even studied abroad in Hungary under a program for US students started by Pal Erdos. He died a week before we were to meet him. :( He was the greatest living mathematician at the time and it was quite sad for mathematicians everywhere that he died. Of course I was very disheartened because I was very much looking forward to meeting him.