164 Are the Androids Dreaming Yet? Mathematicians have catalogued the universe of problems into classes rather as biologists have catalogued animals into species. Each problem is examined and put into a genus with a name. Sadly the names are not as readable as the Latin names for animals. For example, ‘nlogn’ is the complexity class of most sorting programs, while traversing a maze typically sits in the class NP or P/POLY. Although the classifications look complex the basis of cataloging is simple, a class name signifies the time needed to solve a problem using the best possible algorithm, and the scale this is measured in is “Big O° Big O Every problem has a complexity. In mathematics this is expressed using ‘Big O’ notation, where ‘O’ stands for order-of-magnitude. The simplest problems have order 1. If I am working at my computer on a Word document and I press print, the printer will spring to action and print the document. This problem is of flat complexity, notated O(1). It does not matter how large the file is; one click is all I need. I am, of course, assuming sufficient paper in the printer and ink in the cartridges. The next complexity class is a linear problem, O(n). For example, walking to the store to buy a pint of milk. The farther the store, the longer the walk. The time needed to get to the store is directly proportional to the distance: if ] am walking, a single step multiplied by the number of steps required to cover the distance. You might think adding two numbers together is a linear problem — the bigger the number, the harder the problem — but there's a clever trick to speed it up. You can get 10 people to add each column in parallel. They'll need to coordinate when someone ends up with a number larger than ten and has to carry the extra digit but this can be easily solved. A problem gets its classification only once we’ve used the cleverest possible trick to solve it. Most problems we meet in mathematics are somewhere in between flat and li