If someone could prove that P = NP, the world would become a profoundly different place. All encryption mechanisms would be rendered obsolete, and the person would gain the ability to access any password-based banking system in existence. If a person could prove P = NP, the applications to biology would be enormous. Seemingly impossible protein-folding problems would suddenly be solvable, and we would probably be able to cure cancer.
So what do P and NP mean?
Simply put, P and NP are both terms used to describe sets of problems. P problems are easy for computers to solve, whereas NP problems are easy to verify. For example, a Sudoku puzzle is in NP because it takes a long time to solve but, if one were to have the solution, a Sudoku Puzzle could be verified in a short amount of time. You may be thinking that Sudoku puzzles are easy to solve, as computers can solve 9x9s in several milliseconds. But what about 100 x 100? 10,000 x 10,000? The reason Sudoku is in NP is because of the way worst-case running time increases.
The entire problem, and its implications, are explained very well here.
Now onto more personal thoughts.
*
Maybe it was the music, or the calm voice, or the fact that the topics that had frustrated us so much a few hours before the final exam could now be laid to rest, and we could just thoughtfully watch videos like these (assuming we all passed. Damn, I really hope we all passed) with nothing at stake.
Or maybe it’s the greater feeling, the liberating idea that there’s so much we still don’t know about this world, about the constructs of nature and science and even of the greater implications of the computers we have built. Undergraduate education is all about coming up with the right answers, answering A when A is correct or 7 when 7 is correct. What if the system were somehow able to avoid this? What if we focused more on what we didn’t know, like children exploring a new playground for the very first time?
I don’t really think it’s possible now…at least not as undergraduates in STEM fields. There are times when creativity and questioning are the way to go, but not in grinding upper-division and weeder classes like these.
So this is it for now. This is the little indulgence we get to have…a little unanswered question and a taste of philosophy before we hit the textbooks once again.