HOUSE_OVERSIGHT_015858.jpg

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. I’ll 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
sketch.

The Complexity Hierarchy
My table below represents the hierarchical complexity of knowledge.
We start off with the problems both humans and computers find easy,
then rapidly move onto problems that even the fastest machines find
difficult: a perfect game of chess or predicting the weather. Above these
computable problems are the non-computable ones which no computer

HOUSE_OVERSIGHT_015858