Exercise

• Describe the state space for tic-tac-toe (noughts and crosses).
• How big is it?
• Note that you need adversarial search algorithms for noughts and crosses.
• There are many (say n) cities that a travelling salesman needs to go to.
• He can only go to each city once, and wants to travel the shortest distance.
• Describe the search space.
• How big is it?
• This is an NP-complete problem, and there is a lot of work done with it for trucking companies.
• One of the 10 great open mathematics questions is "is NP equivalent to P"?