[Computational Complexity] Fringe Science
- We caught the season premiere of Fringe over the weekend. The opening credits have words describing the "Fringe Science" topics the show will deal with such as Teleportation, Precognition, Nanotechnology and Artificial Intelligence. I half expected to see Quantum Computing on the list.
The movie had various stock science characters, the crazy professor locked in an insane asylum for the last 17 years and his son, who once lied about his credentials to be a chemistry professor and managed to get a few papers published before he was caught.
The son said at one point the father would have to solve "mixed integer programs" for his conscious sharing process. When I hear mixed integers I think of odds and evens living side-by-side in perfect harmony.
But after some Googling, turns out Mixed Integer Programming is a variation of linear programming where some of the variables are constrained to be integers and even has its own workshop MIP. MIP generalizes integer programming and is thus NP-complete. So the take-away message from Fringe is
You need to prove P=NP to communicate with the dead.
Posted By Lance to Computational Complexity at 9/16/2008 01:03:00 AM