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.