The Millennium Prize Problems are seven unsolved mathematics problems that The Clay Mathematics Institute of Cambridge, Massachusetts (CMI) chose in celebration of the transition to the new millennium. In the year 2000, CMI chose these seven problems and decided to offer a prize of $1 million per problem to the person who could find a solution. Obviously, these mathematical problems are extremely difficult: only one award has been given, and it took ten years for that to happen! The first – and only, so far – person to solve a millennium problem is Dr. Grigoriy Perelman, who resolved the Poincaré conjecture. Apparently, Dr. Perelman was awarded and declined both the Millennium Prize and the Fields Medal for his proof. While Dr. Perelman managed to resolve the first of the millennium problems, other mathematicians were not so successful. In August 2010, HP Lab researcher Vinay Deolalikar circulated a claimed proof of P ≠ NP in resolution to the P versus NP millennium problem. Even though the proof received much attention from the press and on the internet, and even though the proof was well-written in a historical context, academics spurned this proof because its was seriously lacking in some of its conceptual arguments. According to Finite Model Theory expert Neil Immerman, the proof’s “domain… does not express all of P” (Lipton).
The millennium problem I found most interesting was the P versus NP problem because it’s an important problem in computer science (and I like anything that has to do with computer science). According to the Clay Mathematics Institute, a P versus NP problem essentially asks if any mathematical problem exists such that its answer can be easily checked with the help of a supercomputer, but is impossible to solve by any direct process.
The “P” signifies that a problem is easy to solve while the “NP” signifies that a problem is easy to check. The CMI website gives an example of an NP problem in which you have to create a list of dorm-mate pairs from a pool of 400 students, but you can only choose 100 students and there are certain restrictions as to who can room with whom. This problem is NP, or rather “easy to check”, because if I made a list of 100 students, my friend could easily check if the list fulfilled all the requirements of a solution to this problem. Apparently there are more solutions to this problem than there are atoms in the universe, which makes it seem impossible that we could ever build a supercomputer smart enough to go through and write out every list possible.
The “P” signifies that a problem is easy to solve while the “NP” signifies that a problem is easy to check. The CMI website gives an example of an NP problem in which you have to create a list of dorm-mate pairs from a pool of 400 students, but you can only choose 100 students and there are certain restrictions as to who can room with whom. This problem is NP, or rather “easy to check”, because if I made a list of 100 students, my friend could easily check if the list fulfilled all the requirements of a solution to this problem. Apparently there are more solutions to this problem than there are atoms in the universe, which makes it seem impossible that we could ever build a supercomputer smart enough to go through and write out every list possible.
Works Cited
Lipton, Dick. "Fatal Flaws in Deolalikar’s Proof?" Gödel's Lost Letter and P=NP. 12 Aug. 2010. Web. 1 Nov. 2010. <http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/>.
No comments:
Post a Comment