Packing is Hard

Recently there has been some talk about a computer science problem and a, possible, proof that P doesn't equal NP. The proof of if P and NP are the same is one which I think that every computer science student must have a vague suspicion that they could prove when they first hear about it in their computational complexity course. Perhaps as a consequence of this, undergrads are told that they're not going to work it out as "lots of very clever people have tried to show it and failed".



As an aside, the work around showing P and NP being different or the same is a great example of the scientific method at it's best: all the experts generally agree that P isn't the same as NP, but that doesn't stop them from going through any proof which concurs with that belief with a fine-tooth comb. There is a such a clear separation of believe and the need for formal proof that there's a $1 million dollar prize available for a proof that shows P is the same as or different to NP.



Given that few of us are likely to win that prize, why should everyday people care about if P is the same as NP. The simple answer is that it is applicable to many everyday problems, such as packing a bag. NP stands for 'nondeterministic polynomial time' which is a very complex way of saying that, when given a solution to an NP problem, you can easily show it is a correct solution to the problem. In the case of packing a bag this is as simple as seeing that they've fitted all the items into the bag.

A problem which is 'P' is a 'polynomial time problem', which is to say that finding a solution from scratch is as easy to find as showing that a solution is correct to an NP problem. So if it was to be shown that P problems are not the same as NP problems then it would confirm that it really is sometimes easier to solve a problem when you've got the solution.

On the other hand, showing that P isn't the same as NP doesn't help practical everyday computing. The vast majority of polynomial time problems still take too long to solve with current computing technology, so all a proof would show is that there are very very hard problems as well as very hard problems. Most importantly, showing P isn't the same as NP certainly won't stop your word processor crashing when you've forgotten to save for 10 minutes.