The Andrews-Curtis conjecture and black box groups

The paper discusses the Andrews-Curtis graph Δ_κ(G, N) of a normal subgroup N in a group G. The vertices of the graph are κ-tuples of elements in N which generate N as a normal subgroup; two vertices are connected if one of them can be obtained from another by certain elementary transformations. This object appears naturally in the theory of black box finite groups and in the Andrews-Curtis conjecture in algebraic topology [3]. We suggest an approach to the Andrews-Curtis conjecture based on the study of Andrews-Curtis graphs of finite groups, discuss properties of Andrews-Curtis graphs of some classes of finite groups and results of computer experiments with generation of random elements of finite groups by random walks on their Andrews-Curtis graphs.