The University of Michigan Combinatorics Seminar
Fall 2002
October 4, 4:10-5:00, 3866 East Hall

A topological approach to the game of "20 questions"

Robin Forman

Rice University


In the usual game of 20 questions, one player tries to determine a hidden object by asking a series of "yes or no" questions. A number of real life search problems have this general form. However, in applications one is usually limited to a predetermined set of questions, and one is not required to determine the hidden object precisely, but rather only to determine the object up to some sort of equivalence.

For example: Suppose one has a communications network, and a storm (or a terrorist attack, or...) knocks out some of the arcs in the network. For each arc of the network, one may test "Is this arc still working?" (This is the predetermined list of allowable questions.) The goal may not be to determine the surviving network precisely, but instead to determine the answers to a small list of questions of the form "Is the network still connected?" "Is there still a direct connection between Point A and the Point B?", etc.

In the problems we examine, we will assume that one can complete the task if one is permitted to ask all of the allowable questions. The question we will examine is - Is it possible to do better? That is, can one complete the task without asking all of the allowable questions?

Our approach is to restate the problem in a more topological form. We will then define a new homology theory that captures the difficulty of solving this problem. The link between the homology theory and the original search problem is provided by a slight generalization of "Discrete Morse Theory."