Futurama: "Bender's Big Score" + other movies/"new" episodes

[disjunction]

[ QUOTE ]
Well I learned something new. I read Wiki on P vs. NP until this sentence:



Then my head started to hurt and I had to lie down.

[/ QUOTE ]

[ QUOTE ]
Don't feel bad, I googled it, opened the wiki page and then died a little inside when i didn't understand wtf they were talking about.

[/ QUOTE ]
Just saw these questions. If I answer it with a thread it will get moved to SMP and you won't see it. So, since 2 people asked, and it's in Futurama, and I'm sure this thread will return to Futurama, and it might come up again, I'll elaborate a little. There's nothing head exploding about P vs NP. To understand it, you need to understand what we mean by "complexity class" when we say complexity class P.

A complexity class gives a bound on how many steps a program needs to solve a type of problem. (Formally, when we say "program" we mean a specific type of program called a Turing Machine, but we'll ignore that and say that the program is just a regular program on your computer). Let's look at a problem like the clock game on "The Price Is Right". Say I pick a number from 1 to 100, you make a guess, and I say "higher" or "lower", and you guess again. How many guesses do you need? Your first guess is 50, then 25, etc, so it turns out you only need something like log(100) guesses. For the generic problem, replacing 100 by n, you would need log(n) guesses.

Similarly, scanning a nxn grid can be said to take on the order of n^2 steps.

We say that a problem is a member of Complexity Class P if we can express the number of steps we need to get to a solution as bounded by some polynomial. Seems pretty powerful, right? But lots of problems can't be bounded even by a polynomial. Take cards. The combination of cards in the deck is 52x51x50x49x48... . Suppose that instead of a 52 card deck we used an n-card deck. Then the number of cards that could come out would be something similar to 2^n. So considering every possible card sequence is not in P (for an n-card deck).

Now let's look at a different problem, subset-sum. The problem is this: Given a set of n numbers, does any subset add up to zero? You can see intuitively that this problem isn't in P, in order to say "No", you'd need to take every number, then every second number, etc. Thus, you'd need to check 2^n combinations before saying "No".

But let's define a special type of program that might be able to do this quick. We call this program Nondeterministic. There are a few ways to view this type of program. One is that it is a program that always makes lucky guesses. Given the subset sum, it always guesses the first number correctly, then the 2nd number, etc. A more conventional way of viewing a Nondeterministic Program, is that at each step it spawns as many new programs as it wants, and each program makes its own guess. The program finishes when these spawned programs can give a conclusive answer. Now, it is easy to see that Subset Sum can be solved in a polynommial amount of time with this super spawning program? We call this type of problem NP.

It turns out there are a lot of NP problems. Furthermore, it turns out that they are all interchangable, if I can write a program to solve one in a polynomial amount of time, I can solve them all. For instance, if I were clever enough, I could probably turn some card game into Subset Sum, solve the Subset Sum problem, and convert the solution back to a card solution.

Believe it or not, though, nobody has proved for sure that the NP problems are not solvable in a polynomial amount of time! Thus, we are left with the question, does P = NP? As you can see from above, it sure seems likely that they are not equal, but we can't prove it.

To anyone who has read this far, and did not know the concepts, I hope this helped. To anyone already familiar with this, if I made a mistake feel free to correct.