tag:blogger.com,1999:blog-3722233.post3491657201461522956..comments2008-09-16T18:18:06.593-05:00Lancehttp://www.blogger.com/profile/06752030912874378610lance@fortnow.comBlogger5125tag:blogger.com,1999:blog-3722233.post-62837102011113824982008-09-16T18:18:00.000-05:002008-09-16T18:18:00.000-05:00If 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87147957119840537542008-09-16T08:06:00.000-05:002008-09-16T08:06:00.000-05:00"You need to prove P=NP to communicate with the dead..."<BR/><BR/>efficiently. 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.Amitabhahttp://www.cse.iitd.ernet.in/~bagchi/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89989405805886063342008-09-16T04:56:00.000-05:002008-09-16T04:56:00.000-05:00Steve: 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.) <BR/><BR/>Therefore "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.David Molnarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81505921712584852812008-09-16T03:26:00.000-05:002008-09-16T03:26:00.000-05:00Yeah, when they started talking about Mixed Integer Programming the entire room here at MIT cracked up. I had no idea it was real.Harrisonhttp://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50442201308151447992008-09-16T01:45:00.000-05:002008-09-16T01:45:00.000-05:00Reminds 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.<BR/><BR/>Ah, here we are: <A HREF="http://www.goldengryphon.com/atrocity-frame.html" REL="nofollow">The Atrocity Archives</A> is the first book in the series. A bit of a delight for escapist computer scientists.Steve Shanerhttp://www.cs.iastate.edu/~smshanernoreply@blogger.com