Recently, slashdot went berserk with Vinay Deolalikar’s manuscript (in progress) that claims P is not equal to NP. For a detailed generalist’s explanation of the P vs. NP problem, check out MIT’s website. Now many of you might ask “WTF is P, NP, and why should I care?” I am here to tell you that whoever you may be, you should care about it, and I will explain why.
Here are links to various sections of the post, so that readers familiar with certain topics can skip them:
- Definitions of P and NP
- If P=NP, the good
- If P=NP, the bad
- If P=NP, the ugly (philosophical implications)
- If P=NP, the irrelevant
Definitions of P and NP
First, let’s start with definitions. What is P and NP? These are terms from computer science that refer to difficulty of solving certain problems. At the risk of oversimplification, P refers to the class of problems that are ‘easy’ to solve (wikipedia has a more detailed explanation). Examples include addition, multiplication, finding shortest path from city A to city B, and so on. NP refers to the class of problems whose solutions are ‘easy’ to verify (but solving the problem need not be easy). For example, consider the game of Sudoku: while solving large Sudoku puzzles takes a lot of skill, given a filled-out Sudoku board, it is a fairly easy job to verify whether or not the board has been filled out correctly. This is an example of an NP problem (wikipedia article on NP). Note that all problems in P are also in NP.
Here I have to pause and emphasize that ‘easy’ in computer science doesn’t mean easy in the vernacular sense, or at times, even in practice. Please read the wikipedia articles on P and NP for a more detailed explanation.
The outstanding problem of our times in Computer Science is whether every problem in NP is also in P. That is, given a problem whose solution can be easily verified, can the solution be easily found as well? The Clay Mathematical Institute is even offering $1M to anyone who can solve it! Naturally, there have been several (unsuccessful) attempts, several views on the subject.
Great! So it is a problem for computer scientists, why should you care? To answer that question, let us look at the consequences for both P =NP and P != NP. [Back to top]
If P=NP, the good
If P=NP, then you could live in a potential utopia. Why? Because may challenging problems in science and technology are in NP and being able to solve them “efficiently” will pave way for things like a very quick understanding of our genome and protein folding. It will enable postal and courier services to schedule and route our packages is the most efficient way possible to minimize their costs and potentially passing the saving on to us. This can enable huge franchise stores like Walmart, Bestbuy, McDonalds, and other’s to manage their logistics so efficiently that 99c for a burger and $500 for a laptop could seem like price gouging! And these are just two examples of many, many more! Great, right! So we’d ideally want P to be equal to NP, right? [Back to top]
If P = NP, the bad
Well, there’s a dark side to this as well. See, as it turns out many of the “secure” encryptions in use today make use of a problem that is known to be in NP but no efficient solution for it exists. This problem is that of factorization. Given the candidate factors for a given number, it is easy to verify if they multiply to given you that number. If for large numbers, it is currently very difficult to find factors. If P = NP, then it is only a matter of time before factorization becomes easy, and all your credit card data, your usernames and passwords, your back account details, practically everything you thought was secure is available to anyone! Cryptography as we know it is dead! Of course, I am sure other methods of cryptography will be invented, but until then, our secrets are all sitting ducks! [Back to top]
If P =NP, the ugly
Unfortunately, that’s the least of the our problems if P =NP! Can you think of anything that is easy to verify but difficult to solve? How about golf? How about Tiger Wood’s ability to play those amazing shots when everyone else around him, despite their best training and skill, can’t seem to match his genius? While we all can verify that Tiger Wood’s golfing shots are masterly, verify few of us can really accomplish the same thing. That is, we can verify if someone is a genius very efficiently, but we can’t be geniuses ourselves very efficiently or quickly. So philosophically speaking, if P was equal to NP, then if we can appreciate a genius, then we can become one! That would reduce a genius to an average person and elevate and average person to a genius! That leaves little to wonder about creativity. Anyone who can appreciate Joe Satriani could become a master guitarists “easily”! How dull would that world be!
Here’s another ‘issue’: How may of you can come up with a new proof for the Pythagoras’ Theorem? How many of you can verify that a given proof for the Pythagoras’ Theorem is correct? See, as it turns out, verifying a proof, even for many complex claims and assertions, is much easier than actually coming with a proof. So ‘theorem proving‘, as it is called, is in NP, and proof verification is in P. But if P were equal to NP, we all could be mathematicians, physicists, and scientists and prove everything (that can proven within a reasonable amount to space, say a few hundred pages). In fact, we could even write a computer program to prove everything about the world. Not only would all of us eventually be out of a job because computer and robots would be able to do everything, even our lives would be boring and depressing because there are no intellectual pursuits left. Computers have solved everything we care about. That would make the entire universe a very dull place, philosophically speaking.
So I am really looking forward to the claim that P is not equal to NP actually being true! [Back to top]
If P=NP, the irrelevant
Ok, maybe I am being a little hyperbolic over this, because there are still many problems that are not only difficult to solve, they are even difficult to verify. Lets take chess as an example.
Given a Chess board in the middle of a game, and it was black’s move. If I told you that “bishop to C6″ is the best move to make, would you be able to verify it quickly? Maybe if it was near the ending, but in the middle of the game, it is very difficult to verify it! Why? Because Chess is even more difficult than NP. So rest assured, even if P=NP, it will still be a while before a computer beats humanity at chess.
But it does bring up an interesting question. Are there multiple levels of creativity? Is there one kind of creativity that allows us to recognize geniuses when we see them because we, as non-geniuses, can verify their creativity quickly (the kind of creativity that is in NP), and another kind of creativity that we cannot even verify efficiently? What does that even mean? Should we just have to take the creative person’s word for it that what he/she produces is, in fact, creative, and that they are indeed geniuses?
I would love your opinions on it.
[Back to top]
Comments are disabled for this post