Search

We discuss the time complexity of the word and conjugacy search problems for free products G = A ⋆C B of groups A and B with amalgamation over a subgroup C. We stratify the set of elements of G with respect to the complexity of the word and conjugacy problems and show that for the generic stratum the conjugacy search problem is decidable under some reasonable assumptions about groups A, B, C. [ABSTRACT FROM AUTHOR]

We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group. [ABSTRACT FROM AUTHOR]

We introduce a family of multiplicative distributions {μ[sub s]|s∈(0,1)} on a free group F and study it as a whole. In this approach, the measure of a given set R⊆F is a function μ(R) : s → μ[sub s](R), rather then just a number. This allows one to evaluate sizes of sets using analytical properties of their measure functions μ(R). We suggest a new hierarchy of subsets R in F with respect to their size, which is based on linear approximations of the function μ(R). This hierarchy is quite sensitive, for example, it allows one to differentiate between sets with the same asymptotic density. Estimates of sizes of various subsets of F are given. [ABSTRACT FROM AUTHOR]

The paper discusses the Andrews–Curtis graph Δ[sub k](G,N) of a normal subgroup N in a group G. The vertices of the graph are k-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. [ABSTRACT FROM AUTHOR]