168 Are the Androids Dreaming Yet? Imagine you wanted to find the center of a maze. Is there a way to speed searching the maze, so you do not have to test every branch? If you can provide a mathematical proof that there is or is not, you win the prize. Places Game While it is commonly assumed NP problems are the hardest, this is not the case. There are quite a few that are harder still. One such is called a PSPACE problem. It’s quite difficult to explain but luckily many of you will have played a form of it on long car trips when you were a child: My family calls it The Places Game. I will pick a place —- “London; and you must then pick another place, say, ‘New York, that starts with the letter my place ends with. Pll then pick ‘Canterbury’ and my kids will laugh at my dyslexia and I'll have to switch to ‘Kansas’ and so on. Once you use a place you can’t use it again. The mathematical question is to predict who will win given each player has a finite list of places they know? It turns out this type of problem is even harder to solve than an NP problem. This is because on each turn a player gets to pick any name from their list. With the traveling salesman problem, there is only one ‘player’ — the salesman - so we can write out a route and check it. In the Places Game there is no single route through the game because, after I pick my favorite town ‘London; you can pick any place beginning with ‘N’ I have to anticipate an enormous table of possible paths through the game. The table takes huge physical space — which is where PSPACE gets its name. Remember I’m just playing the simplest mathematical games with bits of paper and discrete ideas. I haven't strayed into the quantum world yet. That brings with it a whole new level of complexity to explore. Complexity is such a diverse subject that Scott Aaronson of MIT has created a web site called the complexity zoo to catalogue all the different ‘species. It is much to complex to reproduce here but let me provide a sk