Wednesday, May 21, 2008

Wednesday Math, Vol. 24: NP complete

A lesson to recall from yesterday's post. In math, finite doesn't mean small. There is a finite number to compare the size of a galaxy to the size of a storm, but it's ginormous.

Today I am going to give as non-technical a description as possible of the idea from computer science known as NP-complete. These are a bunch of problems that are related to one another, but no one has found a "nice" algorithm for any of them. The cool thing is that if anybody can find a "nice" solution for one of them, it can be turned into a "nice" solution for all of them. (I'm going to take the quotation marks off of nice for the rest of the post, hoping it won't run away. Recall that finite can be ginormous, which isn't nice. Nice means finite and of reasonable size, or at least reasonable for a computer.)

In computerese, an algorithm is a method. Like any mathematical word, there is more to algorithm than a single sentence comparing it to another better known word. The method has to guarantee stuff, like that it will always give the right answer and it will always take a finite number of steps and a finite amount of time.

The difference between problem and instance. A problem is a general thing, like giving map instructions. An instance is a specific example. Google maps or Mapquest are algorithms for solving the problem of giving directions. Any particular set of directions you get from them to get to grandma's house is an instance of the problem. (By the way, map instructions is an "easy" algorithm that has nice solutions.)

NP complete problems are "hard" problems that are related. A lot of different problems are in the category called NP-complete. The way they are related is that you can take any instance of one problem and translate it into an instance of another problem in a nice amount of time, and translating it back is also possible in a nice amount of time. It's been proven that both Tetris and Minesweeper are NP-complete problems. How can you possibly turn a game of Tetris into a game of Minesweeper?

I say this with love, hypothetical question asker. Don't ask.

But the whole idea is that if any NP-complete problem gets solved nicely, they are all solved nicely but the following steps.

Step 1: Translate your NP-complete instance into an instance of the solved problem.
Step 2: Solve the instance.
Step 3: Translate it back.

Hard to solve but easy to grade. It might be difficult to come up with a solution to some instance of an NP-complete problem, but checking to see if that solution is correct can be done in a nice amount of time. Think about multiple choice tests. They can be very challenging, as anyone who has taken the SAT or GRE will attest, but because they are multiple choice, machines can grade them lickety split.

Good growth and bad growth. As instances of problems get larger and more complex, they take longer to solve. Sometimes that "longer" isn't so bad, and fast computers, which can now perform billions of instructions per second (shortened to bips) can tackle even very large instances and finish them in nice amounts of time.

But some problems take amounts of time that grow very fast. If time grows exponentially, for instance doubling every time a new variable is introduced, that would be very bad indeed. Even worse than exponential growth is factorial growth.

Looking at the map above, let's say we wanted to take a round trip that went to all the cities list above in the shortest possible driving distance. There are 21 cities, so there are 20!, pronounced 20 factorial, different routes. 20! = 20 * 19 * 18 * ... * 3 * 2 * 1. It's about two times ten to the eighteenth power.

If we instead put up the 48 state capitals in the contiguous U.S., there are 47! possible routes, which is about two times ten to the fifty-ninth power.

Even bips can't help us.

By the way, the round trip problem is known as The Traveling Salesman Problem, and is one of the classic NP-complete problems.

Matty Boy and the NP-complete. Am I using my mathiness trying to solve the NP-complete? Aw, hellz no! Instead, since we know that great puzzle games like Tetris and Minesweeper are NP-complete, I've been trying off and on for a few years to turn classic NP-complete problems like Subset Sum and 3SAT into fun puzzle games.

I've succeeded into turning them into puzzle games. The fun part is more elusive.

Yay, Flags of Many Lands™! Yay, Palestine!

You might remember that The Economist magazine predicted that George W. Bush was the best hope the Palestinians had for a two state solution.

I wish the Palestinians better luck than that. No one on this earth deserves George W. Bush as their best hope.


ken said...

Good post, Matt.

For readers out there who might wonder, there _is_ a precise, technical definition of "nice". I think our esteemed narrator was right not to go there. If you're masochistic enough to want to know, Wikipedia has a pretty good set of articles on the subject.

- ken

dguzman said...

Wasn't that the magazine that claimed on its cover that Chimpy was the ONLY man who could bring peace to the Middle East? As if.

Matty Boy said...

Thanks for the kind words, Ken.

You are correct, dg. The Economist title used the word ONLY in that sentence.

He's like Obi-wan Kenobi or something, right?

Distributorcap said...

i have a bigger question? why would anyone want to go to Topeka? travelling salesman or not --

Matty Boy said...

Be nice, Dcap. My dad is from Topeka.

Then again, he is from Topeka and not going back to Topeka, so you may have a point.