Title: Breadth-first search and the Andrews-Curtis conjecture
Speaker: George Havas (Queensland)
Abstract: Andrews and Curtis conjectured in 1965 that every balanced presentation (i.e. with an equal number of generators and relations) of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. Their conjecture was originally motivated by topological questions. Computational work by Miasnikov and Myasnikov on this problem is based on genetic algorithms. We show that a computational attack based on a breadth-first search of the tree of equivalent presentations is also viable, and seems to outperform that based on genetic algorithms. It allows us to extract shorter proofs (in some cases, provably shortest). We also discuss short potential counterexamples.