This is a cross-post from the DeveloperFusion news site.

Remember the Travelling Salesman Problem (TSP)? I hope you’re sitting comfortably.

Yesterday news emerged of an HP researcher who has claimed that he has proved that P != NP.

The P=NP problem is one considered so fundamental to the future study of computer science that the Clay Mathematics Institute assigned it as one of its Millenium Prize Problems, and anyone who can solve the problem is in line for $1,000,000.

The question of P=NP is one of algorithmic complexity. The P stands for polynomial time – so a solution to an algorithm may be verified in O(n^2) time for example. NP stands for Nondeterministic Polynomial time. The problem arises when you have a theoretical algorithm that it is computationally easy (i.e. in polynomial time) to prove a given solution, but finding one of the actual solutions from the start is computationally hard. A common example is this: Given a set A of 10 random positive and negative integers, do the numbers in the set B (where B is a subset of A) sum to zero? If someone gives you a set B then it is extremely easy to verify – you add the numbers together and see if they equal zero or not (it is O(n) time). However, finding a set of numbers that meet the requirement is computationally more complex.

Now, on to the Travelling Salesman. TSP is what’s called an NP-Complete problem. That is, any NP problem can be transformed to the TSP problem in polynomial time. That means, if we can prove that the TSP problem can be solved in polynomial time (or, P=NP), then any NP problem can be solved in polynomial time, via a transformation to the TSP problem.

It remains to be seen whether or not peer scruitiny of the researcher’s paper reveals any flaws in the proof. I took a look at it last night, and I’m not ashamed to admit that most of the introduction was beyond me. It uses a combination of advanced mathematics and physics principles to bring about a proof that P is in fact not equal to NP, and therefore there is no way to solve the NP problems in polynomial time.

You can grab the paper now from Scribd, if you’re feeling brave.

It’s very rare that we get a peek inside the core algorithms and programs that Google uses to manage its worldwide data needs. So when we do, it’s often fascinating and cryptic at the same time.

I have recently been reading the papers that Google have released about various components of their system, particularly BigTable. I also discovered recently this presentation [PDF] given by Jeff Dean, a Google Fellow, on Google’s infrastructure, systems, and processing statistics that I found extremely interesting for a number of reasons.

The first reason I found it interesting is just some of the numbers they are using casually; I thought 300 million realtime Retweet buttons a day at work was impressive – it’s nothing!

The other reason I found it interesting was this is the first mention I’ve heard of Google Spanner, a product (not a wrench) that it is rumoured they are using internally already. Here’s why it’s interesing.