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.
Reminds me of a fiction series by Charles Stross, a world wherein Alan Turing completes the proof for his theorem on "Phase Conjugate Grammars for Extra-dimensional Summoning." The only way to show P=NP is by summoning demons from the netherworld. The main character in the series is a British bureaucrat/secret agent that carries a PDA filled with algorithmic voodoo.
ReplyDeleteAh, here we are: The Atrocity Archives is the first book in the series. A bit of a delight for escapist computer scientists.
Yeah, when they started talking about Mixed Integer Programming the entire room here at MIT cracked up. I had no idea it was real.
ReplyDeleteSteve: actually, I always interpreted _The Atrocity Archives_ as stating that the demons act in fact as oracles. So in their world it may or may not be true that P = NP, but it is true that with the proper incantations you can query an demon that acts as NP oracle. (Well, actually who knows if they're just NP oracles.)
ReplyDeleteTherefore "feasible" in the _Atrocity_ world is the class of problems in P^NP. Not quite the same thing so far as we know as a world with P = NP, unless I am way out of it (which maybe I am). Presumably Charles Stross is hard at work now on a short story to elucidate the difference.
"You need to prove P=NP to communicate with the dead..."
ReplyDeleteefficiently. Given that they're dead they're probably not in such a hurry that they can't wait for a possibly exponential algorithm to end.
If I recall correctly, the first time mixed integer programming is brought up is when Joshua Jackson is pitching himself to two Middle Eastern men as the right man for their pipeline project. He mentions that they'll need someone who can solve MIPs when they're laying out the pipeline and find that the terrain doesn't match the map (and presumably need to compute a new pipeline path). Interestingly, this might actually be a reasonable application of MIP.
ReplyDelete