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

[pwnsall]

Farnsworth: "Dear Lord! That's over one hundred and fifty athmospheres of pressure."
Fry: "How many athmospheres can the ship withstand?"
Farnsworth: "Well, it's a space ship. So I'd say anywhere between zero and one."

[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.

[CallMeIshmael]

Just as sort of an addendum to disjunction's post:

the "joke" in the ep of futurama (its the one where Fry has his head on Amy's body) revolves around the implications for the past 1000 years.


Basically, the P=NP? problem is one of the most important theory problems in the world today (the CMI has offered 1mil to anyone who solves it). Its not immediately obvious, but moving all those problems into P is likely to be worth a TON of money in efficiency.

Evidently, in the future, they have not only solved the problem that P does, in fact, not equal NP, but are able to file the problems into two binders and put them on the shelf. Basically, the joke is that such a monumental problem has been reduced to nothing of note over time.

[chicken10der]

Bender's Big Score has been leaked online, for those knowledgeable and unscrupulous enough to take advantage

[so sick bro]

I steal mostly everything online, but I am buying this.

[chuckleslovakian]

Just watched this today. [censored] amazing. I already want to watch it again.

[tercet]

Now for more of Everyone loves Hypnotoad....

Awesome movie!

[CallMeIshmael]

really really awesome.

Def. written with a ton of callbacks for the observant fan, but w/ a really fun story for the casual fan.

[blackize]

[ QUOTE ]

I steal mostly everything online, but I am buying this.

[/ QUOTE ]

QFT. Im stealing it right now. But I'll buy a copy when it comes out and likely 3 or 4 more as christmas gifts

[Grue]

wow I thought this was surpremely disappointing. Spoilers

<font color="white">The jokes were flat, the A storyline was pretty dumb, the space battle was dumb, etc etc. Only thing nice about it was the production values. I can't believe they "retconned out" fry/leela in regards to devil hand's. In the end the movie ends with nothing changed just like a normal episode of the show, other than maybe "oh nibbler can talk" except of course his race magically turned from being a bunch of cute asskickers to a race of things that can't beat guys with chairs with their spaceships. Really unfortunate. </font>