You can find computer science everywhere – even in popular Solitaire games and puzzles. Most people have played games like Tetris, Battleships, Mastermind, Tantrix and Minesweeper at some point. In fact, all these games have a link to one of the deepest, fundamental problems remaining in Computer Science. They are all linked to a famous equation that is to do with the ultimate limitations of computers.
The sciences have many iconic equations that represent something fundamental about the world. The most famous is of course Einstein’s E=mc², which even non-scientists have heard of. The most famous equation in computer science is ‘P=NP’. The only trouble is no one has yet proved whether it is true or not! There is even a million dollar prize up for grabs for anyone who does, not to mention great fame!
P=NP boils down to the difference between checking if someone’s answer to a puzzle is correct, as against having to come up with the answer in the first place.
You are so NP!
Computer Scientists call problems where it is easy to check answers ‘NP problems’. Ones where it’s also easy to come up with solutions are ‘P problems’. So P=NP, if it were true, would just mean that all problems that are easy to check are also easy to solve.
Let’s take Tantrix rotation puzzles to see what it is all about. Tantrix is a popular domino-type game using coloured hexagonal pieces like the ones in the image. The idea of a Tantrix rotation puzzle is that you place some tiles randomly on the table in a connected pattern. You are then not allowed to move the position of any piece. All you can do is rotate them on the spot. The problem is to rotate the pieces so that all the coloured lines match where tiles meet – red to red lines, blue to blue lines and so on.
Have a go at the Tantrix rotation puzzle above before you read on.
Easy to check?
A solution is here if you want to check it. In fact you can quickly check any claimed rotation puzzle ‘solution’. All you do (the checking ‘algorithm’) is look at each tile in turn and check each of its edges does match the edge of the tile it touches, if any. If you find a tile edge that doesn’t match then the ‘solution’ isn’t a solution after all. How long would that take to check? With say a 10 piece puzzle there are 10 pieces to check each with 6 edges so in total that is 10×6 = 60 things to check. That wouldn’t take too long. Even with 100 pieces it would be only 600 things to check – 10 minutes if you could check an edge a second. So Tantrix rotation puzzles are NP puzzles – they can be checked quickly.
But can you solve it?
The question is: “Are rotation puzzles P puzzles too?” Can they always be solved quickly if you or a computer were clever enough? You may have found that puzzle easy to solve. It is much harder to come up with a quick way that is guaranteed to solve any rotation puzzle I give you. One way would be to methodically work through every combination of tile rotations to see if it worked. That would take a long time though.
There are 6 positions for the first piece (ways to rotate it), but for each of those 6 positions the second piece could be in 6 positions too … and so on for each other piece. Altogether for a 10-tile puzzle there are 6x6x6x6x6x6x6x6x6x6 (i.e., over 60 million) positions to check looking for a solution (and we might have to check them all). If you could check one position a second, it would take you around 700 days non-stop (no eating or sleeping). That is just for a 10-tile puzzle…now for a 100-tile puzzle – I’ll leave you to work out how long that would take.
It is not what computer scientists call “quick”.
How clever do you have to be?
If P=NP is true it would mean there is a quick way of solving all Tantrix rotation puzzles out there, if only someone were clever enough to think of it. If P=NP is not true then it might just not be possible however clever you are. Trouble is no-one knows if it’s true or not…
Tantrix: Solve one, solve them all
We’ve seen how Tantrix rotation puzzles can show what we mean by the question “Is P=NP?” It turns out Tantrix rotation puzzles are also something called ‘NP-complete’. That means it is one of a special kind of problem.
NP-complete problems are the really hard ones. Some are also really important to be able to solve quickly. For example, suppose you are a taxi driver and wanted your SatNav to be able to quickly work out the fastest circular route that went via a whole series of places you wanted to visit (in any order), getting you back home. Simple as it sounds, it is an NP-complete problem. It can’t be done quickly even by a fast computer. The best that can be done is to come up with a good answer not a perfect one – using what’s known as a ‘heuristic’. There are lots of ways of coming up with such good answers – using Swarm Intelligence is one way, for example. The point is none can guarantee the best answer every time.
NP-completeness is important because if you could come up with a quick algorithm for solving one NP-complete problem, computer scientists know how to convert such an algorithm into one that solves all the other NP problems…P would equal NP…Trouble is no one has so far done it…
– Paul Curzon, Queen Mary University of London, 2007