Breadth-first search and the Andrews-Curtis conjecture
Contribuinte(s) |
J. Rhodes |
---|---|
Data(s) |
01/01/2003
|
Resumo |
Andrews and Curtis conjectured in 1965 that every balanced presentation of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. Recent computational work by Miasnikov and Myasnikov on this problem has been 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) and to consider the length thirteen case for two generators. We prove that, up to equivalence, there is a unique minimum potential counterexample. |
Identificador | |
Idioma(s) |
eng |
Publicador |
World Scientific |
Palavras-Chave | #Mathematics #Andrews-curtis Conjecture #Trivial Group #Group Presentations #Computer Generated Proofs #Balanced Presentations #Trivial Group #C1 #280405 Discrete Mathematics #780101 Mathematical sciences |
Tipo |
Journal Article |