next up previous contents
Next: A remark on the Up: The Andrews-Curtis Conjecture Previous: Balanced presentations of the   Contents

Genetic algorithms and the Andrews-Curtis conjecture

Genetic algorithms and the Andrews-Curtis conjecture[6]
Alexei D. Miasnikov(City College of New York)
Title: Genetic algorithms and the Andrews-Curtis conjecture

Author: Alexei D. Miasnikov
Categories: GR Group Theory
Math Subject Class: 20E05, 20F05, 68T05 (Primary) 57M05,57M20
Journal reference: International Journal of Algebra and Computation,
Vol. 9 No. 6, (1999) 671-686 Comments: 19 pages

    Abstract: The Andrews-Curtis conjecture claims that every balanced
    presentation of the trivial group can be transformed into the
    trivial presentation by a finite sequence of "elementary
    transformations" which are Nielsen transformations together with
    an arbitrary conjugation of a relator. It is believed that the
    Andrews-Curtis conjecture is false; however, not so many possible
    counterexamples are known. It is not a trivial matter to verify
    whether the conjecture holds for a given balanced presentation or
    not. The purpose of this paper is to describe some
    non-deterministic methods, called Genetic Algorithms, designed to
    test the validity of the Andrews-Curtis conjecture. Using such
    algorithm we have been able to prove that all known (to us)
    balanced presentations of the trivial group where the total length
    of the relators is at most 12 satisfy the conjecture. In
    particular, the Andrews-Curtis conjecture holds for the
    presentation <x,y|x y x = y x y, x^2 = y^3> which was one of the
    well known potential counterexamples.

From: Alexei Miasnikov <>
Date: Mon, 21 Apr 2003 21:07:18 GMT (13kb)


    title = {{Genetic algorithms and the Andrews-Curtis conjecture}},
    author = {Alexei D. Miasnikov},
    howpublished = {International Journal of Algebra and Computation, 
                    Vol. 9 No. 6, (1999) 671-686},
    eprint = {arXiv:math.GR/0304306}}

root 2004-05-05