Wednesday, September 23, 2015

Movies and Math: Traveling Salesman

Stay with me on this. We end up at one of my most favorite movies... eventually.

Suppose there are two groups of problems in the world -- ones that are quickly solved, and ones that are quickly checked. Which is a weird way to classify things, but Sudoku is a great example -- it is really easy to see if you filled in the puzzle right, but it takes much longer to solve it.

The thing is... even for computers, it takes much longer.

The crazy thing... is that not only do we not have a shortcut for solving it -- we don't even know if a shortcut exists.

So that's the "P vs NP" question. Which is terrible Math Slang for "does every problem that is quickly checked also have a quick way of solving it?"

The craziest thing... is that this question effects all sorts of stuff. Everything that's encrypted depends on it, because in theory anything can be decrypted if you just have enough time. But without a shortcut, things are 'safe'.

So if someone could prove this, it means that there would be proof that encrypted things could be quickly decrypted and 'unlimited power' and  'all would be lost'. Maybe. Possibly. But it could mean a lot of good stuff, too -- like faster genome sequencing...

This video from a much smarter person does a much much better job explaining it:


All of which is the basis of:

Travelling Salesman

The story of 4 math geniuses and a politician.

The mathematicians have not only solved the P=NP problem, but they've built a magic computer program that will unlock almost anything. So now they sit in a room and argue ethics -- there exists a magic box of power; who should own it.. what sort of oversight should there be.. should they even be allowed to tell anyone it exists.. all they did was create it; but if it's used for evil, won't they be blamed...

In short, it's about the intersection of math, compsci, politics, and ethics.

2 good articles -- one from Wired and one with Heavy Math


Which finally gets us to:

One of my favorite movies from way back. More action than TS but almost the same premise, with an all-star cast and Robert Redford as a completely believable math geek.

Sneakers, it's been way too long. we should hang out. (I'd tell you to text me, but you wouldn't know what that was in 1992..)

No comments:

Post a Comment