What if P=NP?

May 8, 2013 4:44 PM

Travelling Salesman: The Movie
posted by Westringia F. (42 comments total)

A small man can be just as exhausted as a great man.
posted by shakespeherian at 4:47 PM on May 8, 2013

Spoiler: The solution shown in the film won't work at home.
posted by mccarty.tim at 4:51 PM on May 8, 2013 [2 favorites]

Also, I'm upset the website doesn't come up with a new route every time I roll over a node.
posted by mccarty.tim at 4:55 PM on May 8, 2013 [2 favorites]

12:45, restate my assumptions.
posted by lantius at 5:02 PM on May 8, 2013 [10 favorites]

When a trailer is so boring I spent the whole time thinking about the implausibility of the metaphor it offers...
posted by wotsac at 5:03 PM on May 8, 2013 [4 favorites]

Holy shit, if P = NP this means CASP is so over.
posted by benzenedream at 5:07 PM on May 8, 2013 [1 favorite]

Yes yes it sound interesting on paper, but have they considered the statistical performance of films in which P = NP?
posted by hoople at 5:13 PM on May 8, 2013 [4 favorites]

I was actually pretty sure at first that this was an extremely well done parody or something. I'm less thrilled that it's a real movie.
posted by TwoWordReview at 5:18 PM on May 8, 2013 [11 favorites]

It might be possible that the traveling salesman problem actually P but that p=NP is still unknown.
posted by humanfont at 5:19 PM on May 8, 2013

It looks like Primer meets Birdemic.

To be clear, I loved Primer. Birdemic not so much.
posted by Horace Rumpole at 5:22 PM on May 8, 2013 [2 favorites]

The metaphor is sort of right, if unnecessarily weird. NP contains problems that are easy to verify but hard to find the solutions to. If P=NP, it's just as easy to verify certain classes of answers as it is to find them. It's like answering "find me someone who fits my exact requirements" is no harder than "does this person fit my exact requirements?": as if you could just see all possible answers and get the right one "by magic-" turning the sand to glass, I guess.

But, yeah, the trailer looks like a bad parody. I still maintain that someone could make a good movie with the premise "random guy finds easy algorithm to solve NP-complete problems... now what?" in the vein of Primer (random guys develop time travel... now what?). The best part being, it's a "cyber super weapon" that actually is possible, and on the edge of plausible. And what would you do? Responsible disclosure can't possibly work- once people know about it, the internet as we know it will just collapse. Sell your soul to the NSA? Hide it and profit? Hide it, never use it, always wondering if someone else has come across it (and they probably will)?

It might be possible that the traveling salesman problem actually P but that p=NP is still unknown.

Wait, but I thought the travelling salesman problem was NP-complete, that is, if you can solve it, you can solve any other NP problems? Oh, wikipedia says "the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems." And you can reduce any other NP problem to an NP-complete problem by definition- so an efficient solution to the travelling salesman decision problem would provide an efficient solution to any NP problem, and prove P=NP along the way.
posted by BungaDunga at 5:36 PM on May 8, 2013

The trailer does not lead me to think this movie will be good. The actors read their lines like porn stars.
posted by humanfont at 5:39 PM on May 8, 2013 [1 favorite]

How is melting the desert going to be more efficient than running the whole desert through a sieve? Is there a way to melt square miles of sand in situ and time efficiently? Atomic weapons perhaps, but you'd need a fuck ton of them, and might well vaporize the object you're searching for.
posted by wotsac at 5:40 PM on May 8, 2013

Here lies the Travelling Salesman;
The soles worn off his feet.
For what he thought was n.log(n)
Turned out NP-Complete
posted by AndrewStephens at 5:48 PM on May 8, 2013 [17 favorites]

I made it about 3/4 of the way through the trailer before I realized that it wasn't a parody.
posted by zixyer at 5:48 PM on May 8, 2013 [1 favorite]

Did he say "a quid coin"? Why would he say that?

And there's a pretty standard idiom for something hard to find: A needle in a haystack. You could burn down the haystack, and hey presto. That'd work. But noooooooo. Desert full of sand. Melting the sand into glass might solve the visiblity issue, assuming the sand was the sort that makes nice clear glass, but it doesn't solve the problem of the giganticness of a whole freaking desert. And if you do find the coin, then what? It's under an ocean of glass!

I'll just stick with the Maysles bros, thanks.
posted by Sys Rq at 5:59 PM on May 8, 2013

humanfront: perhaps their understanding of the premise is that P(orn) == N(ot)P(orn)?
posted by hoople at 6:00 PM on May 8, 2013 [2 favorites]

Let's not forget the proof that eight equals the letter D.
posted by Blazecock Pileon at 6:02 PM on May 8, 2013 [4 favorites]

I actually solved this problem years ago. If P = NP, you can factor out the common factor of P from both sides of the equation, getting 1 = N. Since clearly 1 ≠ N, it follows that P ≠ NP.

Somehow my brilliant solution to this problem was never recognized by the "authorities", and I continue to toil away as a solitary genius, solving one difficult problem after another.
posted by twoleftfeet at 6:15 PM on May 8, 2013 [11 favorites]

Maybe the "coin in the desert" is an allusion to the famous problem of finding a lion in the Sahara.
posted by mr vino at 6:17 PM on May 8, 2013

> I still maintain that someone could make a good movie with the premise "random guy finds easy algorithm to solve NP-complete problems... now what?"

As someone who loves algorithms and has thought about them almost every day for almost 35 years, I would not want to see that movie.

My reaction: WHO CARES. ;-) Some problems, which most of the time admit of a pretty good solution pretty quickly, might have completely accurate solutions with some degree of celerity.

Pick your battles! That's a dull one.

Consider on the other hand Rudy Rucker's book, "White Light", where the protagonist finds himself in a world where you can directly experience countable infinities. That's one of the trippier books ever written.

Even a world where you could get timely to uncomputable problems would be interesting. But this? Far too abstract.

I'm also not looking forward to the other movies in this vein:

"Color My World (Four Is Enough)."
"The Last Conjecture (Fermat Strikes Back)."
"Spaceballs (Every Simply Connected, Closed 3-Manifold Is Homeomorphic To The 3-Sphere)."
posted by lupus_yonderboy at 6:18 PM on May 8, 2013 [9 favorites]

Spoiler--they not only show P=NP, they show all cases in P are solvable in O(n²) or less. It's FANTASTIC!
posted by hexatron at 6:25 PM on May 8, 2013 [2 favorites]

I enjoyed these movies, really loved the whole series, until Traveling Salesman IV, when they showed that binary search had log₂ time. The movies didn't go downhill, but I thought they were only half as enjoyable with each new release.
posted by twoleftfeet at 6:28 PM on May 8, 2013 [4 favorites]

It might be possible that the traveling salesman problem actually P but that p=NP is still unknown.

No. The Travelling Salesman Problem is NP-complete, which means that an efficient solution for it would be an efficient solution for all NP problems. Hence P = NP.
posted by gkhan at 6:37 PM on May 8, 2013

I completely forgot to write the screenplay for Oliver Sacks and the Amazing Twins. The concept was good though. A doctor is asked to investigate a strange case of autistic twins. These twins, barely able to speak to others, had somehow developed an internal language between the two of them. This language somehow included an ability to factor large numbers, and an astounding recognition of prime numbers.

So far the plot is based on a true story, but to make a good movie, the twins become targets of the National Security Agency, because factoring large numbers into primes quickly defeats some common encryption schemes. The twins run for their lives, and along the way they learn a little about themselves, and we, as the audience, learn a little about ourselves.
posted by twoleftfeet at 6:39 PM on May 8, 2013 [1 favorite]

So it looks like Hollywood is learning. This is the second movie I know of that uses a real hacking tool in the way the hacking tool actually gets used (more or less) (the other one was nmap in the second Matrix movie). The text at around 1:20 is from Metasploit Console, and it seems, with a little fudging, to be the delivery system for the P=NP virus or whatever it is.
posted by scalefree at 6:59 PM on May 8, 2013

scalefree: " This is the second movie I know of that uses a real hacking tool in the way the hacking tool actually gets used (more or less)"

I actually find the use of real tools often leads to an uncanny valley of sorts. At least in The Net you knew the technology references were comically incorrect, so you could focus on what an awful movie it was instead of looking out for technology fails.

I get the same feeling when they use real products in movies -- my brain for some reason has been trained to expect "COLA" in a movie and be surprised if I see "Pepsi."
posted by tonycpsu at 7:12 PM on May 8, 2013

Pretty much all the metals used in coins have a melting point at least a few hundred degrees C lower than that of glass -- depending on its composition, maybe 1600°C. So not only is the metaphor crazy impractical, it wouldn't work at all. By the time the sand turned to glass the coin would have melted and seeped through the gaps in the sand. You'd basically have an amorphous glob of metal mixed into your glass, not a coin.

(I'm also not in the least persuaded that you get clear glass by melting a given body of natural sand either, but that's a slightly less rigorous objection.)
posted by George_Spiggott at 7:51 PM on May 8, 2013 [3 favorites]

Pretty much all the metals used in coins have a melting point at least a few hundred degrees C lower than that of glass

That's a good point. But the melting point of silver is about 961.8°C.
posted by twoleftfeet at 8:02 PM on May 8, 2013

It looks like the P.J. Plauger story "Wet Blanket" crossed with Darren Aronofsky's "Pi: the Movie".
posted by hwestiii at 8:31 PM on May 8, 2013

But the melting point of silver is about 961.8°C.

Not sure I follow. That''s still ~600°C less than that of glass, putting it somewhere in the middle of typical metals used in coinage, ranging from tin at a mere 232°C through nickel at around 1450.
posted by George_Spiggott at 8:34 PM on May 8, 2013

I was also disappointed that this was a parody, because a parody of this idea could have been pretty good, but there's no way they can pull off a straight interpretation of it. (You might say that such a movie is intractible, and argue that P(arody)≠N(on)P(arody).)

It's like answering "find me someone who fits my exact requirements" is no harder than "does this person fit my exact requirements?"

Yeah, and that's why finding an easy way to solve NP-complete problems would mean more than just breaking all crypto, pwning the internet, overthrowing all governments, or whatever other insignificant trivia the movie might present. It would be an overwhelming change in the nature of human experience, like the invention of writing, or at least the invention of math.

(Somewhere on the internet there's an interesting post exploring the idea that the fundamental difference between the zones in Vinge's "Zones of Thought" setting is that P=NP in the higher zones— perhaps there's a way to directly implement nondeterministic automata, or something— and some problem we consider easy becomes intractable in the lower zones.)
posted by hattifattener at 8:34 PM on May 8, 2013

Also, when I found a dynasty my imperial coinage will be tungsten for the smaller denominations and pure iridium for the larger denominations. So there.
posted by hattifattener at 8:36 PM on May 8, 2013

Regarding the crypto superweapon, they already made that movie. It's called Sneakers.
posted by demiurge at 9:05 PM on May 8, 2013 [2 favorites]

IIRC Sneakers' mcguffin was just about factoring large numbers (from what I remember of the lecture scene). That would affect most public-key crypto, but that's about it.
posted by hattifattener at 9:44 PM on May 8, 2013

The melted gold coin will also sink to the bottom of the glass. Which isn't more of of a problem than the fact that its melted, but is not going to make finding and retrieving it any easier. I don't suppose the glass will be very clear either - the sand isn't necessarily pure, and it will probably have all sorts of debris and air bubbles in it. Melting the desert seems like a great way to describe something that sounds slick in a meeting, but which turns out to be a pessimal solution.
posted by wotsac at 9:58 PM on May 8, 2013

It would be an overwhelming change in the nature of human experience, like the invention of writing, or at least the invention of math.

Hah, it's not like if someone discovers that P=NP we'll all immediately undergo some technological rapture to reach a new stage of consciousness. It's more likely that the super-algorithm will have some huge power (e.g., O(n^40) is still polynomial time), making it theoretically important but with little immediate practical impact.
posted by Pyry at 11:13 PM on May 8, 2013

That's why I specified "an easy way", Pyry. Of course if we discover P=NP but with some enormous work factor it wouldn't have much practical impact.
posted by hattifattener at 11:19 PM on May 8, 2013

You are wrong, humanfont. TSP is NP-complete, meaning that (1) P = NP if TSP is in P and (2) TSP is in NP. That's the whole point.

As for cryptography, there is vastly more chance that factoring lies in P than that P = NP. Factoring already lies in both NP and coNP. Factor is quantum polynomial-time. etc.

We believe that P != NP but afaik our current most likely approach for achieving P = NP is building a computer with access to closed timelike curves. Ain't likely.

There are already arbitrarily good polynomial-time approximation algorithms for many NPO-complete problems like TSP, but TSP is actually APX-complete too, meaning you cannot even approximate answers beyond a certain factor unless P=NP.
posted by jeffburdges at 4:02 AM on May 9, 2013 [2 favorites]

Since clearly 1 ≠ N

Except for every now and then.
posted by Twang at 7:01 AM on May 9, 2013

The melting point of the Copper-Zinc-Nickel alloy used in modern British pound coin is right about 1025 C. So yes, significantly lower than the melting point of sand.
posted by mountmccabe at 7:22 AM on May 9, 2013 [1 favorite]

Adding sodium carbonate (soda ash) and calcium oxide (burnt lime) to your desert will allow it to melt at temperatures of just 500°C-600°C.

If you can't find soda ash or burnt lime, try heating up some Sprite. I'm sure that's how it works.
posted by Sys Rq at 7:59 AM on May 9, 2013