Imagine you're going to see your friends on the other side of the world and you've bought them so many presents, you can't fit them all into your luggage — some have to be left behind. You decide to pack a combination of presents that is highest in value to your friends, but doesn't exceed the weight limit imposed by the airline. How do you find that combination?

The knapsack problem. Image: Dake, CC BY-SA 2.5.

The obvious thing to do is to try all possible combinations, calculate their value and weight, and pick one that is below the weight limit but maximises value. This is fine if there are only a few items, but gets hard when many are involved: there are simply too many combinations to try out and your plane is leaving soon. The question is whether there is an algorithm — a recipe for finding a solution — which works for any number of items and doesn't take too long even when many items are involved.

This kind of problem interests computer scientists because creating algorithms, mechanical procedures a computer can execute, is what computer science is all about. Computer scientists have a way of measuring the complexity of a problem in terms of how fast the time it takes to solve the problem grows with the size of the input. For example, suppose the size of the input (the number of presents) is If the time it takes to solve the problem grows roughly like or or or for any other natural number as gets larger, then the problem is deemed "easy". The number could still grow fast with if is large, of course, but this kind of polynomial growth, as it's called, is nowhere near as explosive as exponential growth, described, for example, by the expression . (See here for a more technical definition of so-called polynomial time algorithms.)

So does such a polynomial time algorithm exist for our problem? There's a slightly easier decision version of the problem. Rather than asking "what is the optimal combination of presents that stays under the weight limit but maximises value", we ask "given a particular value V, is there a combination that stays within the weight limit and has a value exceeding V?". This problem has the nice property that given a potential solution (a combination of presents) it's very easy to check that it's correct: you only need to add up the weights and values, and you can do that in polynomial time. However, whether or not a polynomial time algorithm exists to solve the problem from scratch isn't known. This puts the decision version of the knapsack problem into a class of problems called NP.

The hierarchy of complexity classes. The class P contains all those problems that can be solved in polynomial time. The class NP contains all those problem for which a potential solution can be checked in polynomial time. It's possible that the NP class is equal to the P class, though nobody knows if it is, which is why there are two diagrams: one for the case that P=NP and one for the case that it isn't. NP complete problems are within the NP class, but particularly hard, and NP hard problems are at least as hard as NP complete ones. Image: Behnam Esfahbod, CC BY-SA 3.0.

The decision version of the knapsack problem also has another amazing feature: if you do find a polynomial time algorithm to solve the decision knapsack problem, then you'll be able to derive a polynomial time algorithm for every problem in the NP class, which would be quite something. This feature means that the decision version of the knapsack problem belongs to a subclass of NP problems called NP complete. (Confused? See the diagram on the left.)

And the full knapsack problem? Well, it's at least as hard to solve as the decision version of the problem. Even given a potential solution, there's no known polynomial time algorithm that can tell you whether the solution is correct. But as for the decision version of the problem, if you do find a polynomial time algorithm to solve the full knapsack problem, then you'll be able to derive a polynomial time algorithm for every problem in the NP class. The knapsack problem is a so-called NP hard problem.

Optimisation problems such as the knapsack problem crop up in real life all the time. Luckily there are efficient algorithms which, while not necessarily giving you the optimal solution, can give you a very good approximation for it. Thus, the question of whether the knapsack problem can be solved in polynomial time isn't that interesting for practical purposes, rather it's something that enthuses theorists. When it comes to delivering presents, however, our advice is not to buy too many in the first place.

You can find out more about the complexity of algorithms on Plus.