Although 3-colourability is a fairly abstract concept from the fields of complexity and graph theory, most ten year olds will be well familiar with it. The problem relates to the process of colouring in a map of countries with various shapes and sizes. How many different pens do you need so that no adjacent countries are the same colour? 3-colourability, in particular, is to do with whether a certain map can be shaded using only three colours so that there are no borders with the same colour on either side. This writeup will give a simplified introduction and description to the problem, and a more detailed proof of 3-colourability's properties at the end.
Introduction
For fairly small example like this:
+---+---+
|###|&&&|
|###|&&&|
+---+---+
|*******|
|*******|
+-------+
it is fairly obvious that there is no way to complete the map in with two colours, although it is possible with three. However, when it comes to very large examples, such obvious solutions do not spring to mind, and it seems that the only option is to exhastively try every single possible colour arrangement until a winner is found. Although this would work eventually, it's an absolutely massive amount of work to do. Also, to make things worse, the solution produced by this expensive operation would be very easy to verify and seem so obvious; surely if verfication of a solution is easy, there must be a quick way to find that solution?
By now, you may be wondering why some of the greatest minds in the world are putting such effort into find a better way for kids to do their homework. Of course, the map example is just an instance of an underlying problem. Presenting it as a task everyone has attempted just makes it a bit more user-friendly. In a more abstract sense, the 3-colourability problem can be seen as a number of interconnected nodes, each of which cannot share a certain property with any of the nodes it is connected to. This is the sort of problem mathematicians, computer scientists and Everythingians face every day. Everythingians? Well, sort of.
Imagine we have an XP whore, who needs a successful writeup, but can't be bothered to think of a novel topic, let alone research it. He can either node some obscure mathematical concept no-one really cares about or he can reproduce an existing writeup under a different node, and hope that no softlinks will be created between them, which would expose his scam. If there were enough of these XP whores, you could easily imagine a situation where there were only three original writeups in the whole of Everything. If our lazy noder is to pull off his trick, he needs to make sure that no two softlinked nodes have got the same writeup in them, otherwise his game will be up. This everyday problem is another example of 3-colourability.
So 3-colourability is useful, but finding a quick way of solving it isn't exactly a million dollar question is it? Well, yes, it is. 3-colourability belongs to a set of decision problems called NP-complete, and the Clay Mathematics Institute is offering $1m for the first person to find an efficient way of solving NP-complete problems.
Proof that 3-colourability is NP-complete
This section is fairly mathematical, and I will no longer be simplifying things in aid of readability and at the expense of accuracy.
To prove that a language, L is NP-complete, we only need to show that there is an efficient way of simulating another NP-complete language using L. In this proof, we will show that 3SAT, an NP-complete language, can be mimicked by 3-colourability, and hence that 3-colourability is NP-complete itself.
3SAT is a language concerned with Boolean expressions. There are a number of rules these expressions must obey: they must be in conjunctive normal form, have at most three literals in each clause and be satisifiable by some assignment of truth values (the expression can evaluate to true). So for example, the expression
( a | b | ¬c) & ( ¬d | e ) is in 3SAT, but
( a | b | c | d ) isn't. The actual problem is to find a truth assignment to the variables so that the expression evaluates to true
In order to simulate 3SAT with 3-colourability, we have to construct a graph of nodes and edges which is satisfied when 3SAT is satisfied and vice versa. This means we need a graph that can be 3-coloured only when a corresponding expression evaluates to true. For this example, the three colours I will use are called TRUE, FALSE and OTHER. To construct the graph, start with a node, named root which is coloured OTHER. Also, for every variable x in the expression, create a pair of nodes x and ¬x. This pair is connected to each other and the root, to create a triangle for each variable:
root
(OTHER)
-O-
_//|\\_
/ / | \ \
_/ / / \ \ \_
/ / | | \ \
_/ / | | \ \_
/ / | | \ \
O---O O---O O---O
x ¬x y ¬y z ¬z
Note that there is supposed to be only supposed to be three triangles in this graph, made by a variable, its complement and the root node.
If this graph is to be 3-colourable, each of the variable nodes must be coloured TRUE or FALSE, due to the edge to the root and the edge from a literal to its complement.
With this graph in place, we need to add gadgets for every clause containing the literals l1, l2 and l3, where a gadget is:
l1------O
|\
| \
l2------O--O--O
|\
| \
l3------------O--O--------O
c root
(TRUE) (OTHER)
Note that all the literals on the left are also connected to the root node as shown in the first picture, and are either coloured TRUE or FALSE.
This gadget is just like a three input OR gate. If it is 3-colourable, it demands that one of the inputs on the left is coloured TRUE. For example, if the expression consisted of the clause ( x | ¬y | ¬z ) the graph would look like this:
---------
| \
root \
-O- \
_//|\\_ \
/ / | \ \ \
_/ / / \ \ \_ \
/ / | | \ \ \
_/ / | | \ \_ \
/ / | | \ \ \
O---O O---O O---O |
x ¬x y ¬y z ¬z |
| | | |
| | | |
O------------O | |
\ / | |
\ / | |
\ / | |
\ / / /
\ / / /
\ / / /
O / /
| / /
O---------O /
\ / /
\ / /
\ / /
\ / /
O-----/
This is the finished graph for ( x | ¬y | ¬z ). If we can find a way to 3-colour this graph, we have also found a way to satisfy the boolean expression. This is the efficient simulation of another NP-complete language we were looking for. As this graph mimics 3SAT, the process of 3-colouring must be just as complex, i.e. it is NP-complete.