Nobody has proved P=NP


Which are the world’s fastest computers?

The answer is not to be found, I’d guess, in the Top500 list. Instead they are surely to be found somewhere in the US National Security Administration or maybe even in the UK’s Government Communications HQ.

So the fact that David Cameron is calling for the banning of all internet encryption (yes, I know that’s crazy, but he’s said it), tells us that neither of these agencies (which co-operate very closely) has managed to prove P=NP and so reverse the “one way” functions on which internet encryption depends.

It has been suggested that proving P=NP would not, for most of us, make much difference – as although there might be an algorithm available to crack the problems it might be so complex that it’s not much use – but that is where the huge computing power available to the national communications agencies would matter – and so Cameron’s remarks do point even more strongly to no P=NP breakthrough.