P=NP?

Warning: this is another one of those boring essays you won't want to read.

My mom always asks me, "if you know so much about computers, why don't you fix them?" I always explain, (1) I don't know that much about computers and (2) the interesting stuff is more theoretical, or at least stuff that's not directly used. So I tried to explain the great theoretical computer science problem of whether P=NP. I tried and I failed. So now I'm going to try my best to figure out how to explain this problem to the layperson, and my attempt is below. I think computer science like this is as useful to everyone as the basic chemistry and physics everyone learns in high school; even if you don't become a programmer, it's still good to know it.

Computers do things by executing a number of steps in order given a certain input. This is called an algorithm. One example of an algorithm is below, the algorithm to calculate factorial:

Step 0: Get the number that we are going to take factorial of, and store it as x.
Step 1: Set n equal to 1.
Step 2: If x=1, the answer is n. The algorithm is now finished.
Step 3: Multiply n by x and store the answer in n.
Step 4: Decrement x.
Step 5: Go back up to step 2.

Let's look at how this works. Try doing the factorial of 1. After going through Step 1, n=1 and x=1. Then, Step 2 makes the algorithm end, returning 1 as the result. If you use 3 as the value that we're taking the factorial of, the results of series of steps is as follows:

Step 0: x is now set to 3.
Step 1: n is now set to 1.
Step 2: This is skipped, because x does not equal 1.
Step 3: n is now set to 1*3=3.
Step 4: x is now set to 3-1=2.
Step 5: Go to step 2.
Step 2: This is skipped, because x does not equal 1.
Step 3: n is now set to 3*2=6.
Step 4: x is now set to 2-1=1.
Step 5: Go to step 2.
Step 2: x=1 so the program stops. n, which now equals 6, is the answer.

Obviously, this can get tiring quickly, which is why we have computers. But this algorithm will always return the right answer for a factorial for a number 1 or greater.

One thing that you might notice is that we can calculate the number of steps this will take: for any input x>=1, it takes 4x-1 steps. Since 4x-1 is a polynomial equation, we can say that this algorithm runs in polynomial time*. There are lots of different operations that computers do that run in polynomial time. In fact, almost everything is run in a number of steps that can be represented with a polynomial equation. The things that aren't run really slowly. The set of all algorithms that run in polynomial time is written as P, which, of course, stands for polynomial.

For the factorial algorithm, the two variables (n and x) only had one value at a time. But what if we said that a variable can hold more than one value at a time, and we would simultaneously see how things go for all the values? This doesn't make all that much sense, but let's look at a possible algorithm using this technique, an algorithm that factors an integer. This is key in cryptography, where the RSA encryption algorithm depends on this being difficult to do in a regular computer, where all variables only have one value at a time.

Step 0: Get the number you want to factor and store it in x.
Step 1: Set n to some integer between 2 and the square root of x.
Step 2: If x is evenly divisible by n, then n is a factor.

So this can find a factor of a number in just 3 steps. It's much faster than the regular way of doing it with a regular computer. This weird computer that can hold more than one value in a single variable (as done in Step 1) is called a non-deterministic computer, since it's not deterministic what value the variable will hold at any given time. It might be possible to do this algorithm in polynomial time on a regular computer, but computer scientists still don't know how.

Now, if you understand that, you're over the hardest part. The set of algorithms that can be done by this weird computer in polynomial time is called NP, which stands for non-deterministic polynomial. The question is, is there anything that we can do on the non-determistic computer in polynomial time that we can't do on the regular computer in polynomial time? Or is the set of algorithms on a regular computer in polynomial time the same as the set of algorithms on a non-deterministic computer in polynomial time? That is, does P=NP?

---

* Those of you know know about this stuff will tell me, "No, factorial is actually pseudo-polynomial. You're wrong, Dan. Go home." Well, you're right, but it's just for the sake of explanation. For the acute reader who wants to be confused, here's a more in-depth explanation: computers store things in bits of ones and zeros, and a number takes ceiling(log base 2(x)) bits to hold a number. For example, 7 takes 3 bits to hold in a computer. A real polynomial-time formula actually would be able to do its thing in a number of steps that can be represented by a polynomial formula of the size (for example, in bits) of the input. The factorial formula's number of steps is proportional to somewhere around 2^s, where s is the size of the number in bits. But it was just an example.


PS. If you have trouble understanding this, please leave me a comment.