Lee Rigby, Facebook and P != NP

Yesterday, in a cynical ploy, the UK parliamentary committee on intelligence affairs released a report which tried to lay the blame for Fusilier Lee Rigby’s murder on Facebook. This piece explains why that accusation is not only baseless but an attack on all of us.

Yesterday, in a cynical ploy, the UK parliamentary committee on intelligence affairs released a report which tried to lay the blame for Fusilier Lee Rigby’s murder on Facebook. This piece explains why that accusation is not only baseless but an attack on all of us.

In Woolwich, London on 22 May 2013 serving British soldier Lee Rigby was set upon and murdered by two men claiming to be acting in the global jihadist cause. The grisly murder became a major news story and cause celebre. In December last year the two men, both Londoners of Nigerian Christian background, recent converts to Salafi Islam and the jihadist cause, were sentenced to life imprisonment. This week sees the release of a report from the UK parliamentary committee looking into whether British intelligence services, who were aware of both men’s affiliations, could have prevented the murder. The committee exonerated the intelligence services, as is their usual wont, but instead pointed the finger at the US social media mega-corporation Facebook. In one exchange between Michael Adebowale and an unnamed jihadi, Adebowale mentioned his wish to kill a serving British soldier in as public and as shocking a fashion possible. This message, the parliamentary committee now allege, had it been passed onto the intelligence services by Facebook, could perhaps have prevented Fusilier Rigby’s murder.

Of course this particular claim is neither innocent nor accidental. It takes place against the background of the revelations by ex-NSA contractor Edward Snowden about the extent that the US’s NSA and the UK’s GCHQ are already, illegally, recording all of our Facebook, email, and other social media and internet communications. Indeed, there is no suggestion that this information about the Facebook exchange came from anywhere other than the existing records of NSA/GCHQ . This claim then by the UK parliamentary intelligence committee is transparently an attempt to cynically manipulate this case to justify, retrospectively, their blatantly illegal omni-surveillance of all internet and social media usage by the general population. And indeed many critics of that, now openly-exposed, government abuse have stepped forward to criticise the committee’s report on that basis. But there is a deeper problem here which goes to the heart of the whole privacy/surveillance debate in the NSA scandal, linked to current hype in both media, culture and science about “Big Data”, and one of the most intractable unsolved problems of computational complexity, the P versus NP problem.

 

But first we need to go back. In the early 1970s a unit of the IRA in West Belfast located and captured a British Army intelligence depot, the result of the last few years surveillance on the neighbourhood. After the lengthy process of sifting through the voluminous materials, the volunteer intelligence analysts reported to the Provos that there was no need to worry. Despite the, at first sight, frightening level of comprehensiveness and detail of every move and event in the neighbourhood, the huge mass of data was so unfiltered that finding the operationally useful snippets of information in it would be worse than hunting for a needle in a ten-story high haystack. Because of a secret Army intelligence report in the hoard that assessed that the Provos could not be militarily defeated, the find was later made public with much fanfare and became a footnote in the history books. Although the more significant revelation that Army intelligence’s use of mass surveillance and mass collection of data was a dead-end remained private for much longer. Later on MI5 changed the intelligence game through the more tried and tested methods of human intelligence, recruiting informers through bribery and blackmail, running infiltrators and so on, but that’s another story.

 

Of course today in the era of mass computing power, when every pundit is shouting about the powers of “Big Data” to transform the process of knowledge discovery in the fields of science, social policy, commerce and everything in between, you could be forgiven for thinking that the Brit Army Intel’s problem in the early 1970s, was that they were just a bit ahead of their time in terms of available technological capabilities. According to this widely-sold but naive view of the magical powers of “Big Data”, with today’s technology the Brits could have fed all that information about the Ballymurphy paper rounds, milk deliveries, who rescued Mrs Kavanagh’s cat from the tree, and so on, into a gigantic “Big Blue” style computer and, after a bit of crunching, a neat list of the people to be arrested so as to stop the Provos in their tracks would have promptly spooled out. More sceptical folk might rightly feel that things are not quite that simple. But for the purposes of the argument against NSA and GCHQ surveillance of the general public, it’s important to understand exactly why it’s not that simple. And this is where the computational science comes in.

 

The central problem of the theory of computational complexity is to figure out what problems can actually be solved by any possible computer in a reasonable time frame, and which ones cannot. It’s important to understand that some problems can be shown to be impossible to compute in a reasonable time frame, regardless of the technology. For example the maths shows that there are more potential chess games than there are neutrons in the whole universe. The problem of working out every possible game of chess is generally considered to be “intractable”. That is, no matter how fast or powerful our future computers will get, we will just not be able to calculate all the games before the heat death of the universe.

 The categorisation of which problems can be calculated in “reasonable” time and which not, is made by their relation to something called “polynomial time”, the “P” in P versus NP. Without getting too much into the maths, it means for a given problem with an input n, the problem can be solved in an amount of time that is of the order of n to the power x (where n to the power x=2 is n squared, etc). If that sounds like a potentially high rate of increase, there are even faster increasing alternatives where the time to solve is either exponential, like chess – e.g. 2 (or greater) to the power of n – or even factorial – n!. If this is all Greek to you, don’t worry too much, the general idea is that there are some problems that can be shown to be solvable in human time, we call P, and some that just can’t.

 However there are other types of problems that we cannot solve “forward” to produce answers in reasonable time, but we can check already-produced answers “backwards” in reasonable time. That is, if we are given a candidate solution for a problem we can check whether it is a correct solution or not in reasonable, P-time. So NP is the set of problems where producing/enumerating solutions is not possible in P-time, but post hoc verification of candidate solutions, however found, is possible.

In computational theory the great unsolved problem in the relationship of P and NP is whether or not it is possible to show that P = NP, or contrarily, that P is not equal to NP (“!=” is shorthand for “is not equal to”). There’s more than one way to skin a cat, and the same is true for computable algorithms. It is possible, in certain cases, to prove that one algorithm carries out the same computation for all inputs as another. Even if one algorithm is vastly more efficient than  the other. The great hope in computation is that if you have one algorithm that is exponential time (intractable), that you might somehow find a way to transform it into a functionally equivalent but more efficient algorithm that works in P-time (tractable).

The great unsolved problem of the P and NP relationship then, is can we find a magic algorithm “Z” that can be used to transform any NP algorithm into a P one? This would both prove that in reality P = NP, and solve all of our forward computability problems for the existing, known set of NP problems. Unfortunately (or perhaps fortunately, as we’ll see in a minute) so far we have no candidates for this magic “Z” algorithm and so, for our existing level of knowledge and technology P != NP. Big Data may have done many wonderous things in its harnessing of statistical analysis and data mining to large data sets to find previously undetected correlations. But it is not magic and it has not solved the problem of transforming NP into P.

If you think that this is the kind of thing that only computer scientists are interested in, you would be wrong. The whole of the digital encryption technology upon which the internet relies, is based on encryption algorithms which rely on certain properties of prime numbers, including the NP problem of distinguishing prime numbers from non-primes. Given a particular number, verifying whether it is a prime or not is a P problem, but trying to produce all the primes is, at the moment, an NP problem. If this was ever to change, all of existing digital encryption and internet security would be effectively broken. So the P vs NP problem is wholly at the centre of the NSA and GCHQ’s attempt to break encryption and spy on the world. Which is why, when we say that the argument for increased internet surveillance being advanced by NSA/GCHQ advocates is a nonsense in light of P != NP, we can be sure that they are well aware of the fact. In other words that the parliamentary report on the Rigby killing is an exercise in cynicism not ignorance.

Let’s return from the realm of abstraction to the real world. Last month a 16-year old Leeds schoolboy was sentenced for murder of one of his teachers, Ann Maguire. Despite all the usual speculation that swirled around how an otherwise ordinary teenager could have ended up as a cold-blooded killer, the consensus from both mental health professionals and social commentators was fairly clear. There is simply no way of telling apart the one in a million teenagers who moves from occasional expressions of violent fantasies, to actually carrying out murder, from all the others. Finding the one teenager who went on to be a killer from all those that once said “I really want to f***ing kill that ****!” is an NP problem – easy to make the link in retrospect, impossible to predict going the other way.

The same applies to filtering out which of the ISIS-groupies on the internet are going to move from talking “big” on the internet into actually carrying out “lone wolf” style terror attacks. Of course the mercurial nature of teenagers is a much more commonly experienced reality to most of the population, whereas jihadi-groupies are a much more marginalised phenomena. But even though smaller in number, the problem of predicting which individual from even a small mass of blowhards will actually move to action, is no less intractable. Facebook has no more possibility of finding a magic formula for solving this particular NP problem than GCHQ or the NSA and considerably less resources to do so, if truth be told.

So if reliably picking out future lethal threats to civilians from mass surveillance of social media and internet usage by ordinary civilians is a computational impossibility, and the NSA and GCHQ know it, why do they want their powers for mass snooping so badly?

The answer is simple – power. Snooping on everybody will not reliably aid you find future terrorists that you don’t yet know about, but it sure is a great way of giving yourself power over anybody that might at some time in the future give you reason to want to damage them – for exposing your illegal spying on the public, for example. Or maybe for protesting against the inalienable right of white US police officers to gun down unarmed African American youth with impunity.

The reason for targeting someone is at your discretion when your power is hidden and unaccountable. It is for this that the NSA and GCHQ fight. And it is this arbitrary and tyrannical use of mass surveillance that we need to confront with the science that the one single reason given to justify this power – the protection of the public from attack by so far undetected evil-doers – is the one purpose that this power is useless for. P != NP. Mass surveillance cannot protect us from attack by fellow civilians and is, in itself, an attack on all civilians by unaccountable state power.