##
The Complexity of the Reachability Problem for Tournaments

Till Tantau

Fakultät für Elektrotechnik und Informatik

Technische Universität, Berlin

tantau@cs.tu-berlin.de
### ABSTRACT

A group of knights have gathered to hold a tournament that consists of
a series of jousts between every pair of the knights. After the
tournament Sir Lancelot and Sir Galahad meet and Sir Lancelot says, ``I
liked your style. It is only fair you won our joust.'' Sir Galahad
answers, ``I am not so sure. I think you won a joust against someone
who won against someone who won against someone, and so forth, who won
against me. Isn't that true?'' The two knights ponder on this, but it
seems difficult to answer as there were so many jousts. So they go to
Merlin, the magician, and pose their problem. Merlin consults his
crystal ball, which lets him see into the future, and proclaims: ``If
some of the jousts in the tournament ended in a draw, your question is
difficult to answer. But if none of them did, there is an extremely efficient
algorithm to solve it.'' This talk is about that algorithm.

After a short introduction to descriptive complexity theory, I will show that
the tournament reachability problem is first order decidable and has hence
very low computational complexity. In particular there exists a family of
constant depth, unbounded fan-in circuits for this problem. This shows that
deciding reachability for tournaments is provably easier that deciding it for
trees or dags. As a corollary we obtain that the succinct tournament
reachability problem is in the polynomial hierarchy. In sharp contrast,
succinct reachability problems for most other kinds of graphs are known to be
complete for polynomial space.

Professor Till Tantau is currently visiting the Department of Computer Science
at the University of Rochester.

Colloquia Series page.