Title: The word and conjugacy problems in lacunary hyperbolic groups,
Abstract: We study the word and conjugacy problems in lacunary hyperbolic groups
(briefly, LHG). In particular, we describe a necessary and sufficient condition
for decidability of the word problem in LHG. Then, based on the graded
small-cancellation theory of Olshanskii, we develop a general framework which
allows us to construct lacunary hyperbolic groups with word and conjugacy
problems highly controllable and flexible both in terms of computability and
computational complexity.
As an application, we show that for any recursively enumerable subset
$\mathcal{L} \subseteq \mathcal{A}^*$, where $\mathcal{A}^*$ is the set of
words over arbitrarily chosen non-empty finite alphabet $\mathcal{A}$, there
exists a lacunary hyperbolic group $G_{\mathcal{L}}$ such that the membership
problem for $ \mathcal{L}$ is `almost' linear time equivalent to the conjugacy
problem in $G_{\mathcal{L}}$. Moreover, for the mentioned group the word and
individual conjugacy problems are decidable in `almost' linear time.
Another application is the construction of a lacunary hyperbolic group with
`almost' linear time word problem and with all the individual conjugacy
problems being undecidable except the word problem.
As yet another application of the developed framework, we construct infinite
verbally complete groups and torsion free Tarski monsters, i.e. infinite
torsion-free groups all of whose proper subgroups are cyclic, with `almost'
linear time word and polynomial time conjugacy problems. These groups are
constructed as quotients of arbitrarily given non-elementary torsion-free
hyperbolic groups and are lacunary hyperbolic.
Finally, as a consequence of the main results, we answer a few open
questions.