Elementary S02E02 - Solve for X
Spoiler alert: Netflix inverted the order of S02E02 and S02E03. If you just watched the second episode on Netflix stop reading now and watch the next episode first.This episode revolved around an algorithmic problem that was solved by mathematicians. Although there are minor nits, the computer science was pretty accurate. Interestingly, this was one of the few story-lines where the authors seem to underestimate the impact and potential of their premise.
P vs NP
In this episode Sherlock investigates the death of two mathematicians that seem to be close to solving the problem of "P vs NP". In this section I will try to explain in layman's terms what P vs NP tries to solve.Basically, it boils down to the question if it is possible to write a computer program that can pack a knapsack efficiently: given a knapsack of a certain size and items of specific size and value, what is the subset of items that fit in the knapsack and maximize the value? (The actual NP question is, if the knapsack can be filled with items in such a way that a specific value is reached, but let's not get pedantic.)
 |
| "Knapsack". Licensed under CC BY-SA 2.5 via Wikimedia Commons - http://commons.wikimedia.org/wiki/File:Knapsack.svg#mediaviewer/File:Knapsack.svg |
Unfortunately "all possible combinations" explodes with the number of items that are available. With 5 items we have to try 32 combinations, with 10 items 1024, and with 20 items we are already at 1,048,576 combinations.
The question if there is a (significantly) better way than trying all possibilities is the question "P vs NP". If it is possible, then "P = NP". If it is impossible then "P ≠ NP".
Most scientists believe that P ≠ NP, but nobody was able to prove it so far. Just proving the answer (a simple "yes" / "no") would be worth a million (the Millenium Problems price). However, proving that P = NP would automatically solve a few other millenium problems and net in a few more millions. "Just" proving P = NP still wouldn't mean that you could solve the knapsack problem, though. You could a) just have a non-constructive proof that it is possible without knowing how, or b) have a way to solve the problem which is significantly better than the current solution of trying all possibilities, but, one that would still be too slow to be practical.
In the Elementary episode we had the most exciting outcome: an efficient solution to the problem.
Why so exciting? Knowing how to pack a knapsack is important and one might even see similar problems in other domains, but is it really worth killing for? And wasn't there a mention of cryptography in this Elementary episode? How are these connected?
Let's be clear: it's hard to imagine the (practical and monetary) value of an efficient solution to the problem. With a good algorithm it would suddenly be possible to make huge advances in medicine, artificial intelligence, and almost every area in computer science.
The connection to (public) cryptography is less obvious, but actually quite simple: with relatively little work we can translate a decryption of a public key into a knapsack problem. In fact, computer scientists have started (already in the 1970s) to collect problems that are related: "if I could solve this problem, then I could also solve that other problem". Wikipedia, for example, has a (partial) list of NP-complete problems (the ones that Knapsack is in), but there are many many more. It turns out, that knowing how to solve the knapsack problem automatically allows one to break a public encryption key (although nobody has proved so far that the inverse is true).
The P vs NP problem is fascinatingly simply and has far-reaching consequences. Accordingly, lots of brilliant scientists have worked on it, but nobody was able to solve it yet. Surprisingly, we might never get an answer. The episode only mentions this in passing (at ~13:25): "P vs NP may well be unsolvable", but it is definitely a possible outcome. In fact, Gödel proved in 1931 that some (valid) theorems simply cannot be proved: Gödel's incompleteness theorems.
Further reading:
Status of the P Versus Np problem
If I just proved that P=NP how do I start taking over the world?
Review
Although this episode was pretty good there is still room for some nitpicking... |
| Sherlock finds a security camera that was tracking the victim. |
That said, it's not unimaginable that there was a return channel (for example to zoom, or focus differently). In that case it is indeed possible to triangulate the signal source of the "receiver" (which then would be a sender). However, by disconnecting the camera, Sherlock would have made it much harder (if not impossible) to find the controller, which would probably just turn off itself.
The discussion with the security firm person was pretty good, but the idea of hiding the P = NP solution to come up with a new cryptography system feels wrong.
- any public cryptographic system is broken if P = NP (with an efficient algorithm). To my understanding there is no real way around this.
- non-public cryptographic systems are safe. In the very worst case there is always the one-time pad which is provenly unbreakable (but harder to manage).
I definitely wouldn't call it a "child's play", but it might be possible. An efficient solution to P = NP would allow the attacker to break public cryptography. A computer that does nothing but record security footage has no use for that. However, if that computer also transmitted the data to another computer, or if the cameras were connected via wifi, ... there might be a way in. It seems to me that just finding a computer that can be reached somehow is the hardest part. In most cases a normal exploit (not relying on P = NP) would probably be easier for attacking the machine.
Finally, the idea that the NSA just takes everything related to the problem (including Tanya Barrett) unfortunately seems completely plausible to me. I doubt it would be to "[protect] the country against her break-through", though.
Comments
Post a Comment