Elementary P v. NP

“What’re you currently binge-watching?” is a great conversation-starter, I think. One well-suited for this age and carrying enough insights into the person you’re trying to strike up a conversation with.

I’m currently binge-watching Elementary, an adaptation of Sherlock Holmes whose mysteries may not be as well-roundedly gripping as they are in Sherlock but whose narrative spares me the melodrama of Benedict Cumberbatch and whose reality is neither as ambitious nor paranoid. I also like the idea of a male-female pair in the lead that doesn’t have sex from the get-go.

But in its simplicity, Elementary sometimes get ahead of itself. The most common symptom of this is that, in a few episodes, there is some information that is revealed in the second-half, to which the viewer has had no previous access and so to whom the resolution veritably arises from the blue. As a once-avid quizzer, this is a buzzkill because it offers no opportunity for the viewer to attempt to solve the puzzle before Holmes does (which isn’t impossible). It also makes a lesser ‘deductionist’ of Holmes because, in the viewer’s eyes, it robs him of the ability to piece together a solution to a puzzle using pieces the viewer knows exist.

But in some other episodes, another kind of problem arises. In them, Elementary ventures into fantasy. Often it has the good sense to explain some conundrums away with the suffix “… if we had a really well-equipped lab and billions of dollars”. At other times, it assumes the viewers ignorant. And at even other times, it clubs the two.

An example of the last variety is season 2, episode 2: ‘Solve for X’. In this episode, two mathematicians are killed while they’re both working on a solution to the P versus NP problem. The problem, first formally presented by a computer scientist named Stephen Cook in 1971, asks whether P equals NP. P stands for the set of all problems that can be solved in a reasonable amount of time (relative to their complexity). NP stands for the set of all problems that cannot be solved in a reasonable amount of time but that can be verified in a reasonable amount of time.

(John Pavlus had the perfect metaphor for NP back in 2010: “Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it”.)

Though a solution to the problem has evaded the most skilled mathematicians for many decades, most of them intuitively believe that P ≠ NP. Solving the problem fetches a $1 million cash prize from the Clay Mathematics Institute (CMI), New York – setting up the motive in ‘Solve for X’. However, the episode is also careful to note the fact that most of modern cryptography is problem-solving and that a solution to the P v. NP problem would be worth hundreds of millions to digital security companies.

This is a line that was bandied about just last month when a group of physicists announced that they were a step closer to resolving the Riemann hypothesis, another mathematical problem that carries a $1 million reward from the CMI. Resolving the hypothesis has some beautiful implications for the incidence of prime numbers on the number line and for prime factorisation, both integral components of the RSA encryption algorithm. However, it says little about how a problem itself could be solved – a notion that is also applicable to the pop culture surrounding the P v. NP problem.

In ‘Solve for X’, a third mathematician solves the problem and then uses it to hack emails and into CCTV footage.

Proving that P equals NP does not mean programmers immediately have insights into where the solutions for a given problem may lay. They only know that, technically, the problem has a solution in polynomial time. For example, consider the RSA algorithm itself. It is effective because it relies on prime factorisation, the process of finding two large prime numbers whose product is being used as a key to cracking the security the algorithm affords. A single-core 2.2-GHz CPU is supposed to take “almost 2,000 years” to factorise a number with 768 bits. Numbers with 2,048 bits or higher are thought to be unfactorisable in a single human lifetime. At the same time, given two prime numbers, their product can be quickly computed and a proposed solution rapidly verified.

But proving P equals NP doesn’t make any of this easier. Knowing that there is a solution out there is not the same as knowing what it could be, particularly in situations where scientists are concerned with practical applications.

R.J. Lipton, an expert on the problem, probably has the most meaningful take on this: that succeeding in solving the problem is about making a psychological impact. If P ≠ NP, then your conception of the world isn’t shaken much: some problems that you thought were hard are going to remain hard. But if P = NP, then it means there are a whole bunch of problems that you thought were hard but are actually easy, and that you – and thousands of mathematicians over the years – have missed out on simpler answers. However, it wouldn’t have anything to say about where this ease arises from.

… unless there is either something encoded in the solution of the P v. NP problem itself or it’s the case that a unified solution emerges to crack all NP problems. I felt that ‘Solve for X’ takes such encoding for granted, that it significantly overestimates the confidence boost accorded by knowing that a problem is solvable or that it significantly underestimates the gap between P = NP and being able to hack into everything. In other words, if P equalled NP, I would still be aghast if someone hacked into Google’s servers.

Any which way, it goes a step too far, evident when you see Tanya Barrett and her programmer friend go from solving the problem to hacking into CCTV footage within a day. It makes a fool of a viewer by saying that this is what the P v. NP problem immediately helps accomplish – and it also makes savants of Barrett and the programmer in order to be able to make such rapid progress but whose savantism doesn’t manifest in any other way.

I also think Elementary may have missed a great opportunity to explore a wider, wilder world in which P = NP.

As with my criticism of Spectral, my taking on of Elementary happened because it was an interesting intersection of science and popular culture and that doesn’t happen often. And while Elementary may not have perfectly depicted the consequences of solving a famous mathematical problem – just the way Spectral took some liberties with depicting an esoteric physical phenomenon – I’m glad that it ventured in that direction at all.

Finally, if you’re interested in reading more about the P v. NP problem, I highly recommend Scott Aaronson’s and Lipton’s blogs. Both can get quite technical but they also have some posts that discuss the problem very well, by which I mean not just simple language but also with insights that might allow you to glimpse the underlying principles. Here are two posts – here and here – to get started with.

Featured image credit: Pexels/pixabay.