This article looks at a famous, but quite abstract, example of a NP problem. For a slightly more accessible description of an NP problem, see here.
Sometimes the truth is binary. There are statements which are either true or false with nothing in between. Examples are "4 is an even number" or "London and Birmingham are less than 200 km apart". There are also statements that aren't quite so binary. Examples include "sloth is sinful" and "cutting taxes is good". Not only are these a matter of opinion, they could also be true in some ways and false in others.
It won't come as much of a surprise that mathematics is very comfortable with statements of the former kind. There's a whole system of logic, called propositional logic, built around them. The system doesn't care about the actual content of such statements. Instead, it tells you what their being true or false means for combinations of them.
As an example, imagine that P and Q are two binary statements — these are also known as Boolean statements after the mathematician George Boole. Then propositional logic decrees that the statement P AND Q is true if both P and Q are true, otherwise it is false. Checking against real life, this makes sense. The statement "4 is an even number and London and Birmingham are less than 200 km apart" is true if and only if both parts are true.
Propositional logic also decrees that the statement NOT(P) is true when P is false and vice versa. This also makes sense. And it means that the statement P AND NOT(P) can never be true, since one of its components will always be false. See this article to find out more about propositional logic.
Here is an example of a composite statement from propositional logic involving three constituent statements A, B, and C:
A AND NOT(B AND C)
For the assignment A=true, B=true, C=false the statement evaluates to true. Hence the statement is satisfiable.
Using the rules of propositional logic you can string individual statements together to your heart's content, giving you composite statements that are as long as you like. (See the box for an example of a statement made up of three components.)
Given such a composite statement, you might ask yourself if it can ever be true: is there an assignment of truth values to its constituent components that makes the overall statement true? If yes, then the statement is considered satisfiable. The problem of finding out whether a given statement is satisfiable is known as the satisfiability problem also often denoted by SAT.
SAT is NP
How do you solve SAT for a given statement from propositional logic? One way is to try out all possible assignments of truth values to its constituent parts. In our example in the box, this would mean trying all ways in which you can assign the values "true" and "false" to each of A, B, and C in the statement, so you would be going through combinations of the form
A=true, B=true, C=true
A=true, B=true, C=false
A=true, B=false, C=true,
and so on. If there are many constituent parts, then this could take an awfully long time — and the longer the statement, the longer it will take.
Indeed, nobody knows of a general algorithm for solving SAT for any given statement whose execution time doesn't explode as the length of statements increases. To be precise, nobody knows of a polynomial time algorithm for the SAT problem (find out more here). Note that "execution time" here doesn't mean the time it takes to solve the problem as measured on a clock — that would depend on the speed of your computer. Instead it refers to the number of steps the algorithm has to execute. Polynomial time algorithms are considered efficient, not because this number of steps is always low, but because it grows in a relatively tame way as the length of the problem increases.
While a polynomial time solution for SAT remains elusive, the problem comes with another interesting feature. If I gave you a possible solution for a given statement from propositional logic — an assignment of truth values to individual components which I claim makes the overall statement true — then checking that this solution is correct is comparatively quick. There is a polynomial time algorithm for doing this.
Problems of this nature, for which a potential solution can be checked in polynomial time, are known as NP problems. There's quite a few of them around. Another example is the decision travelling salesperson problem. Given a list of cities and a distance d, the task is to see if there's a route that visits every city exactly once, returns to where it started, and has length at most d. A brute force solution would involve looking at all possible routes and seeing if one fits the bill. The time it takes to do this will grow very fast as the number of cities grows, but checking whether a given route is a solution is relatively quick. Another example of an NP problem is the decision knapsack problem (find out more here).
SAT is NP complete
How does SAT fit into the jumble of NP problems? Back in the early 1970s Stephen Cook and Leonid Levin independently proved that it can embody them all.
Given any instance of an NP problem (e.g. the decision travelling salesperson problem for a given list of cities), you can create a (possibly giant) statement from propositional logic. If this statement is satisfiable, then the answer to the original NP problem is "yes" (e.g. there is a route of the required length). If the logic statement isn't satisfiable, then the answer to the original NP problem is "no" (there isn't such a route). The translation of the original NP problem to the logic statement can be done efficiently, that is, in polynomial time.
NP problems which have this property — that all instances of all other NP problems can be translated into them in polynomial time — are known as NP complete. SAT was the first NP complete problem to ever be discovered.
Why do we care about all this so much? We said above that nobody knows of polynomial time algorithms for solving NP problems. But this doesn't mean that such algorithms don't exist. If someone were to discover one for an NP complete problem such as SAT, then it would be possible to translate it into a polynomial time algorithm for all other NP problems. Conversely, if someone were to prove that a polynomial time algorithm doesn't exist for an NP complete problem, then this result would apply to all other NP problems too.
This brings us to one of the biggest open problems in all of mathematics: whether the class of NP problems is actually equal to the class of problems that can be solved in polynomial time. The latter class is known as P. The overall problem is called the P versus NP problem. It's one of the seven Clay Millennium Problems: anyone who can solve it will win a million dollars. Find out more here.
This content forms part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI) – you can find all the content from the collaboration here.
The INI is an international research centre and our neighbour here on the University of Cambridge's maths campus. It attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.
