Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{30-MAY-2003,30-MAY-2003,30-MAY-2003,30-MAY-2003}
 
\RequirePackage[warning,log]{snapshot}
\documentclass{era-l}
\issueinfo{9}{06}{}{2003}
\dateposted{June 24, 2003}
\pagespan{40}{50}
\PII{S 1079-6762(03)00110-0}
\copyrightinfo{2003}{American Mathematical Society}
\usepackage{amssymb}
\usepackage{amsfonts}

\newcommand{\nb}{\newblock}
\newcounter{ppp}
\newcounter{band}
\newcounter{annulus}
\newcounter{nonannulus}
\newcounter{ovals}
\newcounter{innermost}
\newcounter{touch}
\newcounter{bigons}
\newcounter{spokes}
\newcounter{derived}
\newcounter{spone}
\newcounter{sptwo}
\newcounter{figone}
\newcounter{ab}
\newcounter{abone}
\setcounter{ppp}{1}
\newcounter{pone}
\newcounter{pdone}
\newcounter{psi}
\newcounter{triple}
\newcounter{sigma}
\newcounter{pdtwo}
\newcounter{pdthree}
\newcounter{pdfour}
\newcounter{pdfive}
\newcounter{pfive}
\newcounter{psix}
\newcounter{pdsix}
\newcounter{pdseven}
\newcounter{pdeight}
\newcounter{pdnine}
\newcounter{pdten}
\newcounter{pdeleven}
\newcounter{pdtwelve}
\newcounter{pdthirteen}
\newcounter{pdfourteen}
\newcommand{\pr}{\pageref}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcounter{aan}
\newcounter{pdfifteen}
\newcounter{pdsixteen}
\newcounter{pdseventeen}
\newcounter{pdeighteen}
\newcounter{pdnineteen}
\newcounter{pdtwenty}
\newcounter{pdtwentyone}
\newcounter{pdtwentytwo}
\newcounter{pdtwentythree}
\newcounter{pdtwentyfour}
\newcounter{pdtwentyseven}
\newcounter{pdtwentyfive}
\newcounter{pdtwentysix}
\newcounter{pdtwentyeight}
\newcounter{pdtwentynine}
\newcounter{pdthirty}
\newcounter{pdthirtyone}
\newcounter{pdthirtytwo}
\newcounter{pdfourty}
\newcounter{p2}
\newcounter{p3}
\newcounter{p4}
\newcounter{p5}
\newcounter{p6}
\newcounter{p7}
\newcounter{peight}
\newcounter{pnine}
\newcounter{pten}
\newcounter{peleven}
\newcounter{ptwelve}
\newcounter{p13}
\newcounter{p14}
\newcounter{p15}
\newcounter{p16}
\newcounter{p17}
\newcounter{p18}
\newcounter{p19}
\newcounter{p20}
\newcounter{p21}
\newcounter{p22}
\newcounter{p23}
\newcounter{move}
\newcounter{adjust}
\newcounter{p24}
\newcounter{p25}
\newcounter{p26}
\newcounter{p27}
\newcounter{p28}
\newcounter{p29}
\newcounter{p30}
\newcounter{p31}
\newcounter{p32}
\newcounter{p33}
\newcounter{p34}
\newcounter{p35}
\newcounter{p36}
\newcommand{\area}{{\rm area}}
\newcommand{\diff}{{\rm diff}}
\newcommand{\Lab}{\phi}
\newcommand{\gr}{{\mathcal G}}
\newcommand{\bgr}{{\bar{\mathcal G}}}
\newcommand{\bm}{{\bar m}}
\newcommand{\bee}{{\bar\eee}}
\newcommand{\hhh}{{\mathcal H}}
\newcommand{\tkk}{{\tilde\kkk}}
\newcommand{\tsigma}{{\tilde\Sigma}}
\newcommand{\tool}{\stackrel{\ell}{\too} }
\newcommand{\bsss}{{\bar\sss}}
\newcommand{\csss}{{\sss\cup\bsss}}
\newcommand{\aba}[1]{{\aaa(#1)\cup\bar\aaa(#1)}}
\newcommand{\ata}[1]{{\Theta(#1)\cup\bar\Theta(#1)}}
\newcommand{\axa}[1]{{\xxx(#1)}}
\newcommand{\br}{{\hbox{br}}}
\newcommand{\yyy}{{\mathcal Y}}
\newcommand{\ttt}{{\mathcal T}}
\newcommand{\kkk}{{\mathcal K}}
\newcommand{\eee}{{\mathcal E}}
\newcommand{\aaa}{{\mathcal A}}
\newcommand{\ddd}{{\mathcal B}}
\newcommand{\CC}{{\mathcal C}}

\newcommand{\LL}{{\mathcal L}}
\newcommand{\bx}{{\bf X}(0)}
\newcommand{\ex}{{\bf E}(0)}
\newcommand{\fx}{{\bf F}(0)}
\newcommand{\bb}{{\mathcal B}}
\newcommand{\topp}{{\bf top}}
\newcommand{\bott}{{\bf bot}}
\newcommand{\vk}{van Kampen }
\newcommand{\eqs}{=~\langle ~\Sigma\ ~|\ ~\rr\rangle}
\newcommand{\h}{\hat{\,}}
\newcommand{\Ker}{\hbox{Ker}}
\newcommand{\Sym}{\hbox{Sym}}
\newcommand{\symm}{^{\hbox{sym}}M}
\newcommand{\gam}{\Gamma}
\newcommand{\ccc}{{\mathcal C}}
\newcommand{\ce}{t}
\newcommand{\pleft}{p_{\hbox{left}}}
\newcommand{\pright}{p_{\hbox{right}}}
\newcommand{\ptop}{p_{\hbox{top}}}
\newcommand{\pbot}{p_{\hbox{bot}}}
\newcommand{\cee}{\alpha}
\newcommand{\dol}{\omega}
\newcommand{\iv}{^{-1}}
\newcommand{\toog}[1]{\to_{_{#1}} }
\newcommand{\rsr}[1]{{\bf R}(#1) }
\newcommand{\bn}{{\bf N} }
\newcommand{\tosg}[1]{\stackrel{*}{\to}_{_{#1}} }
\newcommand{\lel}{{(L_j)_-}}
\newcommand{\rer}{{(R_j)_+}}
\newcommand{\lrg}[1]{\stackrel{*}{\longleftrightarrow}_{_{#1}} }
\newcommand{\too}{\to }
\newcommand{\tos}{\stackrel{*}{\to} }
\newcommand{\lr}{\stackrel{*}{\longleftrightarrow} }
\newcommand{\bs}{U}
\newcommand{\cedd}{$\kappa$}
\newcommand{\dti}{$\Delta$}
\newcommand{\ced}{$\cee$- or $\dol$}
\newcommand{\inn}{\hbox{\bf inn}}
\newcommand{\ann}{\hbox{\bf ann}}
\newcommand{\out}{\hbox{\bf out}}
\newcommand{\Ni}{\prec}
\newcommand{\rr}{{\mathcal R} }
\newcommand{\rrr}{{\mathcal R} }
\newcommand{\xxx}{{\mathcal X} }
\newcommand{\fff}{{\mathcal F} }
\newcommand{\kk}{{\mathcal K} }
\newcommand{\ooo}{{\mathcal O} }
\newcommand{\gc}{{\mathcal G} }
\newcommand{\ww}{{\mathcal W} }
\newcommand{\pp}{{\mathcal P} }
\newcommand{\qq}{{\mathcal Q} }
\newcommand{\sss}{{\mathcal S} }
\newcommand{\mm}{{\mathcal M} }
\newcommand{\nn}{{\mathcal N} }

\newtheorem{theo}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cy}{Corollary}
\newtheorem{prop}{Proposition}
\theoremstyle{definition}
\newtheorem{df}{Definition}
\newtheorem{prob}{Problem}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\renewcommand{\theequation}{\thesection.\arabic{equation}}


\begin{document}

\title{The conjugacy problem for groups, and Higman embeddings}
\author{A. Yu. Ol'shanskii}
\address{Mathematics Department,
Vanderbilt University, Nashville, Tennessee 37240, and 
Mechanics-Mathematics Department, Chair of
Higher Algebra, Moscow State University, Moscow, Russia}
\email{alexander.olshanskiy@vanderbilt.edu \quad 
olshan@shabol.math.msu.su}
\thanks{Both authors were supported in part by
the NSF grant DMS 0072307. In addition, the research of the first
author was supported in part by the Russian Fund for Basic
Research 02-01-00170 and by the INTAS grant 99-1224; the research
of the second author was supported in part by the NSF grant DMS
9978802 and the US-Israeli BSF grant 1999298.}

\author{M. V. Sapir}
\address{Mathematics Department, Vanderbilt University, Nashville, Tennessee
 37240}
\email{msapir@math.vanderbilt.edu}

\date{March 2, 2003}

\subjclass[2000]{Primary 20F10; Secondary 03D40, 20M05}

\commby{Efim Zelmanov}
\begin{abstract} For every finitely generated recursively 
presented group ${\mathcal G}$
 we construct a finitely presented group ${\mathcal H}$
containing ${\mathcal G}$ such that ${\mathcal G}$ is (Frattini) embedded into
${\mathcal H}$ and the group ${\mathcal H}$ 
has solvable conjugacy problem if and
only if ${\mathcal G}$ has solvable conjugacy problem. Moreover, ${\mathcal G}$ and
${\mathcal H}$ have the same r.e.~Turing degrees of the conjugacy problem.
This solves a problem by D. Collins.
\end{abstract}

\maketitle

In 1961, G. Higman \cite{Hi} published the celebrated theorem that
a finitely generated group is recursively presented if and only if
it is a subgroup of a finitely presented group. Along with the
results of Novikov and Boone \cite{Rotman} this result showed that
objects from logic (in that case, recursively enumerable sets)
have group theoretic characterizations (see Manin \cite{Ma} for
the philosophy of Higman embeddings).

Clapham \cite{Cla} (see also corrections in \cite{Va}) was
probably the first to investigate properties preserved under
Higman embeddings. In particular, he slightly modified the
original Higman construction and showed that his embedding
preserves solvability (and even the r.e.~Turing degree) of the
word problem. Valiev \cite{Va} gave a new construction of Higman embedding, and
sketched a
proof of a much stronger result: every finitely generated recursively
presented group $G$ embeds into a finitely presented group $H$ such that the
word problem in $H$ reduces to the word problem in $G$ in polynomial time.
This implies that if the
word problem of a finitely generated group is in P (i.e., can be
solved in polynomial time by a deterministic Turing machine), then
it can be embedded into a finitely presented group whose word
problem is also in P. In \cite{BORS}, Birget, Rips and the authors
of this paper obtained a group theoretic characterization of NP
(nondeterministic polynomial time): a finitely generated group
$G$ has word problem in NP if and only if $G$ is embedded into a
finitely presented group with polynomial Dehn function.

The conjugacy problem turned out to be much harder to preserve
under embeddings. Gorjaga and
Kirkinski\u\i\  \cite{GK}  and Collins and Miller \cite{CM} 
proved that even subgroups of index 2 of
finitely presented groups do not inherit solvability or
unsolvability of the conjugacy problem.

In 1976 D. Collins \cite{KT} posed the following question (problem
5.22): {\em Does there exist a version of the Higman embedding
theorem in which the degree of unsolvability of the conjugacy
problem is preserved?}

It was quickly realized that the main problem would be in
preserving the smallest Turing degree, that is, the solvability of the
conjugacy problem. In 1980, Collins \cite{Collins} analyzed
existing proofs of Higman's theorem and discovered that there are
essential difficulties. If a finitely generated group $C$ is
embedded into a finitely presented group $B$ using any existing at
that time constructions, then the solvability of the conjugacy problem
in $B$ implies certain properties of $C$ which are much stronger
than solvability of the conjugacy problem. Collins even wrote the
following pessimistic comments: ``There seems at present to be no
hope to establishing the analogue of Clapham's theorem. \dots
Furthermore these difficulties seem to be more or less inevitable
given the structure of the proof and probably a wholly new
strategy will be needed to avoid them. For the present the most
one can be hoped for is the isolation of conditions on $C$ that
are necessary and sufficient for the preservation of the
solvability of the conjugacy problem in the Higman embedding."

Recall that a subgroup $\gr$ of a group $\hhh$ is called
\label{Frattinif}{\em Frattini embedded} if any two elements of
$\gr$ that are conjugate in $\hhh$ are also conjugate in $\gr$.
Clearly, if $\gr$ is Frattini embedded into $\hhh$ and $\hhh$ has
solvable conjugacy problem, then $\gr$ has solvable conjugacy
problem.

The following theorem solves the problem of Collins:

\begin{theo} \label{main}  A finitely generated group $\gr$ has
conjugacy problem of recursively enumerable Turing degree $\alpha$
if and only if $\gr$ can be Frattini embedded into a finitely
presented group $\hhh$ with conjugacy problem of the same Turing
degree. In particular, a finitely generated group has solvable
conjugacy problem if and only if it is Frattini embedded into a
finitely presented group with solvable conjugacy problem.
\end{theo}

Consider the case when \label{eee}$\gr=\langle A\ |\
\eee\rangle$ has decidable conjugacy problem and we want to embed
it into a finitely presented group with decidable conjugacy
problem (the case when the conjugacy problem in $\gr$ has an
arbitrary r.e.~Turing degree is similar). The standard idea is to
start with a machine that recognizes the set $\eee$ and then
interpret this machine in a group. Of course we would like to have
a machine which is easier to interpret.  The most suitable
machines for our purposes are the so called $S$-machines invented
by the second author in \cite{SBR} and successfully used in
\cite{SBR},
\cite{BORS},
\cite{talk}. An $S$-machine works with words which can
have complicated structure. Different parts of these words can be
elements of different groups (so we do not distinguish between words whose
respective parts are equal in the corresponding groups). As in
Turing machines, every rule of an $S$-machine replaces subwords
containing state letters by other subwords. The advantage of
$S$-machines is that they are very easily simulated by groups.

Let us start with an $S$-machine which essentially goes back to C.
Miller \cite{Mil} (although Miller did not use $S$-machines).
Assume that $A$ is a symmetric set, that is, it contains the formal
inverses of its elements, and let us embed $\gr=\langle A\ |\
\eee\rangle$ into {\em some} finitely presented group
\label{bargr}$\bar \gr=\langle A\cup Y\ |\ \bee\rangle$ using,
say, the standard Higman embedding. Now consider the $S$-machine
$\mm$ with one state letter $q$ and the tape alphabet $A\cup Y$
regarded as a generating set of the free group, and the
following commands (each command says which subwords of a word
should be replaced and gives the replacement word):

\begin{itemize}
\item $[q\to a\iv q a]$, for every $a\in A\cup Y$, \item $[q\to
rq]$, for every $r\in \bee$.
\end{itemize}
The first set of rules allows the state letter to move freely
along a word of the form $uqv$, where $u,v$ are words from the free
group on $A\cup Y$. Such words are called {\em admissible words}
for $\mm$.

The second set of rules allows us to insert any relation from
$\bee$ into the word (we are also allowed to insert and remove
subwords of the form $aa\iv$ because $A\cup Y$ is a generating set
of a free group).

It is easy to see that a word $qu$, where $u$ is a word over $A$,
is recognized by this machine (that is, the machine takes it to the
word $q$) if and only if $u=1$ in the group $\bar\gr$, that is, if
and only $u=1$ in $\gr$ (because $\gr$ is embedded into $\bar\gr
$).

Now we present the ideas of a Higman embedding based on $\mm$.
Let $T_1, T_2,\dots$, $T_m=W_0$ be an accepting {\em computation} of
$\mm$, that is, a sequence of admissible words such that $T_{i+1}$
is obtained from $T_i$ by applying an $S$-rule of $\mm$, the last
word in this sequence being equal to $q$ in the free group.

Suppose that some words $P_i$ and $P_i'$  over a certain alphabet (it is included in the finite
generating set of the group we are constructing) correspond to this $S$-rule, and modulo some set of group relations $Z$ 
we have, for
every $i=1,\dots,m-1$,
\begin{equation*}P_iT_i=T_{i+1}P_i'\,,\end{equation*}
that is, we have
a \vk diagram with the boundary label $P_iT_i(P_i')\iv
T_{i+1}\iv$. Then $PT_1=W_0P'$, where
$P=P_{m-1}\dots P_2P_1$, $P_i'=P_{m-1}'\dots P_2'P_1'$. The
corresponding \vk diagram $\Delta$ has the form of a {\em
trapezoid} (Figure \theppp).

For example, if we use the $S$-machine $\mm$ described above, then
the presentation $Z$ is easy to describe: for every rule
$\tau=[q\to uqv]$ we have the following relations in $Z$:
$\theta_\tau\iv q\theta_\tau=uqv$, $\theta_\tau a=a\theta_\tau$
for every $a\in A\cup Y$ (the letters $\theta_\tau$ corresponding
to the rules of $\mm$ are added to the generating set). In this
case the words $P_i, P'_i$ are of length 1, and are equal to
$\theta_\tau$.

The words $P$ and $P'$ contain the {\em history} of our
computation, because $P_i$ and $P_i'$ correspond to $S$-rules
applied during the computation. The words $T_1$ and $T_m$ are
 labels of the bottom and the top of the trapezoid.


\begin{figure}[t]
\unitlength=.8mm 
\linethickness{0.5pt}
\begin{picture}(140,59)
\put(30.33,59.33){\line(2,-5){22.00}}
\put(52.33,4.67){\line(1,0){35.67}}
\put(88.00,4.67){\line(2,5){21.67}}
\put(109.67,59.00){\line(-1,0){79.33}}
\put(50.00,10.67){\line(1,0){40.33}}
\put(47.33,17.00){\line(1,0){45.33}}
\put(44.33,24.00){\line(1,0){51.33}}
\put(41.67,32.00){\line(1,0){57.33}}
\put(38.33,40.00){\line(1,0){63.33}}
\put(35.00,48.33){\line(1,0){70.33}}
\put(69.00,1.67){\makebox(0,0)[cc]{$T_1$}}
\put(69.00,8.33){\makebox(0,0)[cc]{$T_2$}}
\put(69.00,14.33){\makebox(0,0)[cc]{$T_3$}}
\put(48.00,7.00){\makebox(0,0)[cc]{$P_1$}}
\put(45.00,14.00){\makebox(0,0)[cc]{$P_2$}}
\put(95.00,14.00){\makebox(0,0)[cc]{$P_2'$}}
\put(92.00,7.33){\makebox(0,0)[cc]{$P_1'$}}
\put(42.67,29.33){\vector(1,-3){1.67}}
\put(97.67,29.00){\vector(-1,-3){1.33}}
\put(57.00,59.00){\vector(1,0){15.00}}
\put(64.67,4.67){\vector(1,0){7.67}}
\put(70.67,55.00){\makebox(0,0)[cc]{$T_m$}}
\end{picture}
\caption{\,}
\end{figure}

\addtocounter{ppp}{1}

If the set of relations $Z$ is chosen carefully (see \cite{SBR},
\cite{BORS},
\cite{talk}), then the converse is also true. Thus the word
$PT_1(P')\iv W_0\iv$ is written on the boundary of a trapezoid if and
only if the word $T_1$ is accepted.

The next step is to consider $N\ge 1$ copies of our trapezoid with
labels taken from different alphabets. For technical reasons
(similar to the hyperbolic graphs argument in \cite{SBR},
\cite{Ol97}, \cite{BORS}) we need $N$ to be even and large enough
(say, $N\ge 8$). Let us choose disjoint alphabets in different
copies of the trapezoid. Then we can glue two copies of the
trapezoid by using a special letter $k$ which conjugates letters
on the right side of the first trapezoid with letters on the
left side of the mirror image of the other copy. Notice that if $P$
and $P'$ are copies of each other then we can also glue the right
side of one trapezoid to the left side of the other without taking
mirror images. Of course the conjugacy relations involving letter
$k$ should be added into the set of group relations $Z$.

Suppose that $T_m$ is equal to $q$, i.e., the word $T_1$ is {\em
accepted} by the machine. If we connect the first copy of $\Delta$
with the second copy, then with the third copy, and finally
connect the $N$th copy with the first copy, using different
letters $k_2,\dots,k_N,k_1$,  we get an {\em annular} diagram, a
{\em ring}. The outer boundary of this ring has label $\kkk(T_1)$
of the form $k_1T_1'k_2\iv (T_1'')\iv \dots$ (here we use the fact
that $N$ is even). The words $T_1', \dots, T_1^{(N)}$ are different
copies of $T_1$. The inner boundary has label $k_1q'k_2\iv
(q'')\iv \dots$ (this word is called the {\em hub}) (
Figure \theppp\
shows the diagram in the case of $N=4$).

We add the hub to the list of defining relations $Z$. Now with
every word $T$ of the form $uqv$, where $u, v$ are words in $A\cup
Y$, we have associated the word $\kkk(T)$, and we see that if $T$
is accepted, then $\kkk(T)$ is equal to 1 modulo $Z$. Again, if $Z$
is chosen carefully, then the converse is also true: if $\kkk(T)$
is equal to 1 modulo $Z$ then $T$ is accepted by $\sss$. Thus we
have an interpretation of $\sss$ in the group generated by the
tape alphabet and the state alphabet of $\sss$, the set $\Theta$,
and the set $\{k_1,\dots,k_N\}$, subject to the relations from $Z$.

The diagram on Figure \theppp\  is called a {\em disk}. The
trapezoids forming this disk are numbered in the natural order (from
1 to $N$).

\begin{center}
\begin{figure}[t]
\unitlength=0.8 mm 
\linethickness{0.5pt}
\begin{picture}(140,59.00)
\put(68.17,34.33){\oval(62.33,49.33)[]}
\put(69.67,33.50){\oval(15.33,13.67)[]}
\put(75.33,38.67){\line(1,1){20.00}}
\put(76.67,36.00){\line(1,1){21.00}}
\put(74.00,28.00){\line(5,-4){21.33}}
\put(97.67,12.33){\line(-6,5){21.33}}
\put(62.67,30.33){\line(-3,-2){25.33}}
\put(64.67,28.33){\line(-3,-2){25.33}}
\put(62.67,36.33){\line(-4,3){25.33}}
\put(64.00,38.67){\line(-4,3){24.67}}
\put(64.00,59.00){\vector(1,0){13.00}}
\put(99.33,28.33){\vector(0,1){13.00}}
\put(65.33,9.67){\vector(1,0){12.00}}
\put(37.00,26.00){\vector(0,1){15.33}}
\put(69.67,33.00){\makebox(0,0)[cc]{hub}}
\put(69.67,17.00){\makebox(0,0)[cc]{1}}
\put(69.67,50.00){\makebox(0,0)[cc]{$\cdots$}}
\put(89.67,33.00){\makebox(0,0)[cc]{2}}
\put(49.67,33.00){\makebox(0,0)[cc]{N}}
\end{picture}
\vspace{-0.3in}
\caption{\,}
\end{figure}
\end{center}



\addtocounter{ppp}{1}


We assume that the copy of the alphabet $A$ used in the first
subtrapezoid of a disk coincides with $A$ itself (the generating
set of $\gr$).

Denote the group given by the presentation $Z$ we have got
so far by $G(\mm)$.

There are several ways to use the group $G(\mm)$ to embed $\gr$
into a finitely presented group. We use a method described in
\cite{talk}.

Consider $N-1$ new copies of the trapezoid $\Delta$. Number these
trapezoids by $2',\dots,N'$. Identify the copy of $A$ (but not $Y$)
and the state letter $q$ in the trapezoid number $i'$ with the
copy of $A$ and the copy of $q$ in the ``old" trapezoid number
$i$. Now glue the trapezoid number $2'$ with the trapezoid number
$3'$ using the letter $k_3$ (as before), then glue in the trapezoid
number $4'$ and so on, but glue the trapezoid number $N'$ with the
trapezoid number $2'$ using $k_1qk_2\iv$ (that will be possible
because, as it turns out, in that case the words $P, P'$ will be
copies of each other). Thus,  conjugation of the letters on the
side of the trapezoid number $N'$ by $k_1qk_2\iv$ gives the
letters of the side of the mirror image of the trapezoid number
$2'$. Let us add the relations used in the new trapezoids and the
conjugation relations (involving $k_i$) to $Z$.

The resulting picture is an annular diagram. The inner boundary of
it is labelled by the hub. If we add the hub to the diagram, we
get a \vk diagram which also looks like a disk but has $N-1$
sectors. The outer boundary of this new disk is labelled by the
word $k_1qk_2\iv V$, where $V$ is the suffix of $\kkk(qu)$ staying
after $k_2\iv$. Thus the word $k_1qk_2\iv V$ and the word
$k_1quk_2\iv V$ are both equal to 1 modulo $Z$, so $Z$ implies
$u=1$. We denote by $\hhh$ the group given by the set of relations $Z$
that we have constructed. 

We have proved that the identity map on $A$ can be extended to a
homomorphism from $\gr$ to the subgroup $\langle A\rangle$ of the
group $\hhh$ given by the set of relations $Z$. It is possible to
show that this homomorphism is injective, so $\gr$ is embedded
into $\hhh$.

Unfortunately, even if $\gr$ has solvable conjugacy problem,
$\hhh$ may have unsolvable conjugacy problem. In fact the
difficulties are similar to those described in \cite{Collins}. Let
us give just one example.

Consider two pairs of words $u_1, u_2$ and $v_1, v_2$ over the
alphabet $A$ (we can view these words as elements of $\gr$). Let
$q$ be the first state letter in $\kkk(qu)$. Consider the words
$W_1=q\iv u_1qu_2q\iv$ and $W_2=q\iv v_1qv_2q\iv$. Suppose that
there exists a word $W(A)$ in the alphabet $A$ such that
$W(A)u_1W(A)\iv =v_1, W(A)u_2W(A)\iv=v_2$. Let
$W(A)=a_1a_2\dots a_k$, $a_i\in A$. For every $a\in A$, let
$\theta(a)$ correspond to the $S$-rule of the form $[q\to a\iv
qa]$. Consider the word
$W(\Theta)=\theta(a_1)\theta(a_2)\dots\theta(a_k)$. Then it is easy
to see that $W(\theta)W_1W(\theta\iv)=W_2$. Thus if the pair
$(u_1,u_2)$ is conjugate to the pair $(v_1,v_2)$ in $\gr$, then
the words $W_1$ and $W_2$ are conjugate in $\gr$. One can also
prove that the converse statement is true. In this example,
pairs of words can be obviously replaced by any $t$-tuples of
words, $t\ge 2$. Therefore, if the conjugacy problem is solvable in
$\gr$, then the conjugacy of $t$-tuples of elements in $\gr$ is
solvable. It is known \cite{Collins} that there exists a finitely
generated group $\gr$ with solvable conjugacy problem and
unsolvable problem of conjugacy for sequences of elements. For
such a group $\gr$ the group $\hhh$ has undecidable conjugacy
problem.

Fortunately, since $S$-machines are easier to simulate in groups
than other types of Turing machines, we can overcome this
difficulty (and many others) by modifying our machine $\mm$ (see
below).

It is important to mention that we cannot allow all parts of the
admissible words to be arbitrary group words. To avoid long
computations without inserting new relation from $\bee$, we had to
require that certain subwords of admissible words stay positive
during the computation. This is a major difference between the
$S$-machine used in the proof of Theorem \ref{main} and the
$S$-machine used in our previous papers.

In order to keep these subwords positive we use a trick that goes
back to Novikov, Boone and Higman (see Rotman \cite{Rotman}). They
used a special letter $x$ and Baumslag-Solitar relations of the
form $a\iv xa=x^2$ for every $a$ in the tape alphabet of the
machine. The idea is that if we have relations $a\iv xa=x^2$ for
all $a\in A$ and a word $u\iv xu$, where $u$ is a reduced word in
$A$, is equal modulo these relations to a power of $x$, then the
first letter of $u$ is positive. Notice that one problem with
using the $x$-letters and Baumslag-Solitar relations is that, since
$N-1$ is odd, we cannot use $x$-letters in the second disk
described above (indeed, otherwise it would be impossible to glue
the $N-1$ sectors together since the words $P$ and $P'$ would not
be copies of each other). Thus we need to consider two
$S$-machines (one responsible for the first disk, the other for the
second disk) which are very similar but have different
``hardware": the admissible words of the first machine must have
positive parts described above, and the admissible words of the second
machine do not have to satisfy this restriction.

Now let us briefly describe the strategy of the proof that the
conjugacy problem in $\hhh$ is solvable. As in our previous papers,
the main tool in this paper is bands (other people call them
``strips", ``corridors", etc.).

In terms of annular (Schupp) diagrams, our task is the following:
given two words $u$ and $v$ in generators of $\hhh$, find out if
there exists an annular diagram over the presentation of $\hhh$
with boundary labels $u$ and $v$. It turns out that any annular
diagram over $\hhh$ (after removing some parts of recursively
bounded size) becomes a diagram of one of three main types: a {\em
ring} (where the boundary labels contain $k$-letters but do not
contain $\theta$-letters, where $k$-letters and $\theta$-letters belong
to the alphabets $\kkk$ and
$\Theta\cup\bar\Theta$, respectively, defined below, and all maximal $\theta$-bands are annuli
surrounding the hole of the diagram), a {\em roll} (where the
boundary label does not contain $k$-letters but contains
$\theta$-letters; all maximal $k$-bands are annuli surrounding the
hole), and a {\em spiral} (where the boundary labels contain both
$k$-letters and $\theta$-letters; both the $k$-bands and the
$\theta$-bands start and end on different boundary components,
and each $\theta$-band crosses each $k$-band many times. Different
methods are used to treat different cases. Roughly speaking, the
study of rings amounts to studying the lengths of computations of our
$S$-machines, the study of rolls amounts to the study of the space
complexity (how much space is needed by the machines during a
computation), and the study of spirals amounts to the study of
computations with periodic history. The $x$-letters and the
Baumslag-Solitar relations allow us to treat the case of rings,
but they cause the main technical difficulties in the cases of
rolls and spirals.

\begin{remark} Notice that even though the conjugacy problem in $\hhh$ is
solvable provided it is solvable in $\gr$, the computational
complexity of the conjugacy problem in $\hhh$ can be higher than
in $\gr$. In particular, the algorithm solving the conjugacy
problem in $\hhh$ uses Makanin's algorithm \cite{Makanin} for
solving systems of equations in the free group. Thus we do not
know whether it is possible to embed any finitely generated group
with conjugacy problem, say, in NP into a finitely presented group
with conjugacy problem in NP.
\end{remark}

Now let us give a precise description of the $S$-machines $\sss$
and $\bsss$ and the group $\hhh$ simulating these machines.

Fix an even number $N\ge 8$. Let $A=\{a_1,\dots,a_m\}$,
$A\cup Y=\{a_1,\dots,a_{\bar m}\}$. The set \label{kkk}$\kkk$ of
state letters of $\sss$ consists of letters $z_j(r,i)$, where $z\in
\{K,L,P,R\}$, $j=1,\dots,N$, $r\in \bee$, $i\in\{1,2,3,4,5\}$.

We also define the set of \label{Basicletters}{\em basic} letters
\label{tkk}$\tkk$ which consists of letters $z_j$, where $z\in
\{K,L,P,R\}$, $j=1,\dots,N$, and their inverses. If $z$ is a basic
letter, $r\in \bee$, $i\in \{1,2,3,4,5\}$, then $z(r,i)\in \kkk$.
If $U$ is a word in $\tkk$ and other letters, $r\in \bee$, $i\in
\{1,2,3,4,5\}$, then \label{uri}$U(r,i)$ is a word obtained from
$U$ by replacing every letter $z\in\tkk$ by $z(r,i)$. The
parameters $r$ and $i$ in the letter $z(r,i)$ or in the word
$U(r,i)$ will be called the $\bee$-coordinate and the
$\Omega$-coordinate of the word.

The set \label{aaa}$\aaa^{\pm 1}$ of \label{Tapeletters}{\em tape letters}
of the machine $\sss$ consists of letters $a_i(z)^{\pm 1}$, where
$i=1,\dots,\bm$, $z\in \tkk$. For every $z\in \tkk$ we define
\label{aaaz}$\aaa(z)$ as the set of all $a_i(z)$, $i=1,\dots,\bm$.

Let \label{tsigmaaaa}$\tsigma$ be the following word (considered
as a cyclic word):
\begin{equation*}
K_1L_1P_1R_1K_2\iv R_2\iv P_2\iv L_2\iv K_3L_3P_3R_3 K_4\iv\dots K_N\iv R_N\iv P_N\iv 
L_N\iv. \label{basehub}
\end{equation*} 
Notice that for every basic letter $z$ precisely
one of $z$ and $z\iv$ occurs in the word $\tsigma$. The word
\label{sigmaaaa}$\Sigma=\tsigma(\emptyset,1)$ will be called the
\label{hub}{\em hub}.

For every $z\in \tkk\cup\tkk\iv$ we denote by \label{zmin}$z_-$ 
the letter immediately preceding $z$ in the cyclic word $\tsigma$
or in $\tsigma\iv$. If $z'=z_-$ then we set \label{zplus}$z=z'_+$.
Similarly we define $z_-$ and $z_+$ for $z\in \kkk$.

The language of \label{adm}{\em admissible words} of the machine
$\sss$ consists of all reduced words of the form $W\equiv
y_1u_1y_2u_2\dots y_tu_ty_{t+1}$, where $y_1,\dots,y_{t+1}\in \kkk^{\pm
1} $, $u_i$ are words in $\aaa(y_i)$, $i=1,2,\dots,t$, and for every
$i=1,2,\dots,t$, either $y_{i+1}\equiv (y_i)_+$ or $y_{i+1}\equiv
y_i\iv$. (Here \label{equiv}$\equiv$ is the letter-for-letter, or
graphical, equality of words.) The projection of $y_1\dots y_{t+1}$
onto $\tkk$ is called the \label{baseadm}{\em base} of the
admissible word $W$. The subword $y_iu_iy_{i+1}$ is called the
\label{sector}$y_iy_{i+1}$-{\em sector} of the admissible word
$W$, $i=1,2,\dots$\,. The word $u_i$ is called the
\label{innerpart}{\em inner part} of the $y_iy_{i+1}$-sector. We
assume that the inner part of any $zL_j$-, $zP_j$- or
$R_jz$-sector of $W$ and $W\iv$ is a positive word ($z\in\tkk$),
that is, it does not contain $a\iv$ for any $a\in \aaa$.

All rules of $\sss$ have the form $[k_1\too v_1k_1'u_1,\dots,k_n\too
v_nk_n'u_n]$, where the projections $k_i$ and $k_i'$ on $\tkk$ will
always be the same, and the $\bee$-coordinates and the
$\Omega$-coordinates of all state letters $k_1,\dots,k_n$ (resp.
$k_1',\dots,k_n'$) will be the same. In addition, each $u_i$ (resp.
$v_i$) will contain only letters from $\aaa(k_i)$ (resp.
$\aaa((k_i)_-)$), $i=1,\dots,n$.

For every word $W$ in the alphabet $\{a_1,\dots,a_{\bar m}\}$ and
every $k\in \tkk$, $W(k)$ will denote the word obtained from $W$
by substitution $a_i\to a_i(k)$, $i=1,\dots,\bar m$.

In order to simplify notation, we shall write a rule $\tau$ of the
$S$-machines $\sss$ in the form 
\begin{equation*}[k_1\too v_1k_1u_1,\dots, k_n\too
v_nk_nu_n;r\too r', \omega\too\omega'],\end{equation*}
where $k_i\in \tkk$,
$v_i$ are words in $\aaa((k_i)_-)$, and $u_i$ are words in
$\aaa(k_i)$. We shall also omit $k$ in $u(k)$ if the value of $k$
is obvious from the context.

Some of the arrows in a rule $\tau$ can have the form
$k_i$\label{tool}$\tool$. This means that the rule $\tau$ can be
applied to an admissible word $W$ only if the inner part of
$k_ik_i'$-sectors and $k_{i''}(k_i)_+$-sectors in $W$ are empty
words and $k_i'=(k_i)_+$, $k_{i''}=k_i$ (i.e., $k_i'\ne k_i\iv$ and
$k_{i''}\ne (k_i)_+\iv$). In that case $u(k)$ and $v(k)$ must be
empty.

Let us expand the definition of $u_\tau(k), v_\tau(k_-)$ to the
base letters not occurring in the rule by assuming that in this
case $u_\tau(k)$ and $v_\tau(k_-)$ are empty.

By definition, to {\em apply} the rule $\tau=[z_1\too
v_1z_1u_1,\dots, z_s\too v_sz_su_s; r\too r', \break\omega\too\omega']$ to
an admissible word $W=y_1w_1y_2\dots w_ky_{k+1}$ means to replace each
$y_i(r,\omega)$ with $v_iy_i(r',\omega')u_i$, reduce the resulting
word, and trim the prefix $v_\tau((y_1)_-)$ from the beginning
and the suffix $u_\tau(y_{k+1})$ from the end of the resulting
word.  The rule $\tau$ is called \label{applicable}{\em
applicable} to $W$ if:
\begin{itemize}
\item[(1)] for every $z\in \tkk$ such that $\tau$ locks $zz_+$-sectors,
the inner parts of $zz_+$-sectors in $W$ are empty words, and $W$
does not have $zz\iv$-sectors or $z_+\iv z_+$-sectors;
\item[(2)] the resulting word $W'$ is again admissible (that is, the inner
parts of all sectors which are supposed to be negative or positive
are such).
\end{itemize}

The rules from $\sss^+\subset \sss$, described below, will be
called \label{pnr}{\em positive}, the inverses of these rules will
be called {\em negative}, and each rule of $\sss$ will be either
positive or negative.

The set $\sss^+$ consists of 10 subsets
\label{somega}$\sss^+(\omega)$, $\omega\in \{1,12,2,23,3,34,4,
45,5, 51\}$.

The set $\sss^+(1)$ consists of rules $\tau(1,\emptyset,i)$, where
$i=1,\dots,\bm$. The rule $\tau(1,\emptyset,i)$ has the form
\begin{equation*}
[\lel\tool \lel,P_j\too a_i P_ja_i\iv, R_j\tool R_j, j=1,\dots,N;
\emptyset\too \emptyset, 1\too 1].\end{equation*}
 The meaning of this set of
rules is that the state letter $P_j$ can freely move (if the
$(\bee, \Omega)$-coordinates are $(\emptyset,1)$, and
$L_j$-letters and $R_j$-letters stay next to $K_j$-letters).

The set $\sss^+(12)$ consists of one rule $\tau(12,r)$ for each
$r\in\bee\backslash\{\emptyset\}$:
\begin{equation*}
[\lel\tool \lel, R_j\tool R_j, j=1,\dots,N; \emptyset\too r, 1\too 2].\end{equation*}
This rule does not insert any tape letters; it simply changes the
$\bee$- and $\Omega$-coordinates of state letters. This rule
prepares the machine for step 2.

The set $\sss^+(2)$ consists of rules $\tau(2,r,i)$, where
$r\in\bee$, $i=1,\dots,\bm$:
\begin{equation*}
\tau(2,r,i)=[L_j\too a_iL_ja_i\iv, R_j\tool R_j, j=1,\dots,N;
r\too r, 2\too 2].\end{equation*}
The meaning of these rules is that they allow the state letters
$L_j$ to move freely while $R_j$ stays next to $\rer$.

The set $\sss^+(23)$ consists of one rule for each $r\in \bee$:
\begin{equation*}
\tau(23,r)=[L_j\tool L_j, R_j\tool R_j; r\too r, 2\too 3].\end{equation*}
The meaning of this rule is that the machine can start step 3 when
$L_j$ and $P_j$ meet (that is when the inner parts of
$L_jz$-sectors are empty).

The set $\sss^+(3)$ consists of one rule for each $r\in\bee$ and
each $i$ from 1 to $\bm$:
\begin{equation*}\tau(3,r,i)=[L_j\tool L_j, R_j\too a_i\iv R_ja_i,
j=1,\dots,N; r\too r, 3\too 3].\end{equation*}
These rules allow the state letter $R_j$ to move freely between
$P_j$ and $\rer$.

The set $\sss^+(34)$ consists of one rule for each nonempty
$r\in\bee$:
\begin{equation*}
\tau(34,r)=[L_j\tool rL_j, P_j\tool P_j, j=1,\dots,N; r\too r, 3\too 4].
\end{equation*}
This rule can be applied when the state letters $L_j, P_j, R_j$
meet together; it inserts $r$ to the left of the state letters
$L_j$, and prepares the machine for step 4.

The set $\sss^+(4)$ consists of rules $\tau(4,r,i)$, $r\in\bee,
i=1,\dots,\bm$:
\begin{equation*}\tau(4,r,i)=[L_j\too a_i L_ja_i\iv, P_j\tool P_j,
j=1,\dots,N; r\too r, 4\too 4].\end{equation*}
These rules allow the state letter $L_j$ to move freely between
$\lel$ and $P_j$.

The set $\sss^+(45)$ consists of one rule for each $r\in\bee$:
\begin{equation*}\tau(45,r)=[\lel\tool \lel, P_j\tool P_j, j=1,\dots,N; r\too
r, 4\too 5].\end{equation*}
The machine can start step $5$ when $L_j$ and
$\lel$ meet.

The set  $\sss^+(5)$ consists of one rule for each $r\in\bee,
i=1,\dots,\bm$:
\begin{equation*}
\tau(5,r,i)=[\lel\tool \lel, R_j\too a_i\iv R_ja_i, j=1,\dots,N;
r\too r, 5\too 5].\end{equation*}
 These rules allow $R_j$ move freely between
$P_j$ and $\rer$.

Finally the set $\sss^+(51)$ consists of one  rule for each $r\in
\bee$:
\begin{equation*}
\tau(51,r)=[\lel\tool \lel, R_j\tool R_j, j=1,\dots,N; r\too\emptyset, 5\too 1].
\end{equation*}

The cycle is complete, the machine can start step $1$ again when
$\lel$ meets $L_j$, and $R_j$ meets $\rer$.

The $S$-machine $\bsss$ is similar to $\sss$, so we only present
the differences between $\sss$ and $\bsss$.

We introduce disjoint copies of sets $\kkk$, $\tkk$, $\aaa$, and
denote them by \label{bkta}$\bar\kkk$, $\bar\tkk$, $\bar\aaa$,
respectively. In order to make $\sss$ and $\bsss$ ``communicate",
we identify $z_j(\emptyset,1)$ with $\bar z_j(\emptyset,1)$, $z\in
\{K, L, P, R\}$, $j=1,\dots,N$, and $a_i(P_j)$ with $\bar a_i(\bar
P_j)$, $i=1,\dots,m$, $j=1,\dots,N$. Notice that we do not identify
$a_{m+1},\dots,a_\bm$ with their ``bar"-brothers $\bar
a_{m+1},\dots,\bar a_\bm$, and we do not identify $a_i(z)$ with
$\bar a_i(z)$ for $z\ne P_j$. Notice also that this identification
of letters makes the word $\bar\Sigma$ coincide with the hub
$\Sigma$.


\label{admbar}{\em Admissible words} of $\bsss$ have the same form
as admissible words of $\sss$ except for the following
differences:
\begin{itemize}
\item All letters are replaced by their ``bar"-brothers. \item We
drop the restriction that certain parts of admissible words are
positive (negative). \item The $\bar K_1z$-, $\bar L_1z$-, $\bar
P_1z$- and $\bar R_1z$-sectors must be empty ($z\in\tkk$). Thus in
every admissible word of $\bsss$ the part between $\bar K_1$ and
$\bar K_2\iv$ contains no $\bar\aaa$-letters.
\end{itemize}

The rules of $\bsss$ are obtained from the corresponding rules of
$\sss$ by replacing every letter by its ``bar"-brother and by
removing letters from $\bar\aaa(\bar z_1)$, $z\in \{K,L,P,R\}$.
Thus rules of $\bsss$ do not insert any $\bar\aaa$-letters in the
interval between $\bar K_1$ and $\bar K_2\iv$, and work in other
parts of the admissible words just as $\sss$.

In order to convert the machine $\sss$ into a list of defining
relations, we need to introduce one more set of letters
\label{xxx}$\xxx=\{x(a,\tau)\ |\ a\in \aaa\backslash
\bigcup_j\aaa(P_j), \tau\in\sss^+\}$.

For every $\tau\in\sss$, we also consider a map
\label{alphatau}$\alpha_\tau$ from $\aaa$ to the free group
generated by $\aaa$ and $\xxx\cup\xxx\iv$. Let $\tau\in\sss^+$,
$a\in \aaa(z), z\in \tkk$. Then
\begin{equation*}
\alpha_\tau(a)=\left\{ \begin{array}{ll} x(a,\tau) a & \hbox{ if
}\ z=K_j, \ j=1,\dots,N,\\ x(a,\tau) a & \hbox{ if } \ z=L_j,\
j=1,\dots,N,\\ a & \hbox{ if }\ z=P_j,\ j=1,\dots,N,\\ ax(a,\tau)  &
\hbox{ if }\ z=R_j,\ j=1,\dots,N.
\end{array}\right.
\end{equation*} 
The definition of $\alpha_{\tau^{-1}}$, $\tau\in \sss^+$, is
obtained from the definition of $\alpha_\tau$ by replacing all
$\xxx$-letters with their inverses.

We expand these maps to all words in the alphabet
$\aaa\cup\aaa\iv\cup\kkk\cup\kkk\iv$ in the natural way (mapping
letters from $\kkk\cup\kkk\iv$ to themselves).

Also with every $\tau\in\sss^+$, we associate a set of letters
\label{thetatau}
\begin{equation*}
\Theta(\tau)=\{\theta(\tau,z)\ |\ z\in \{K_j, L_j, P_j, R_j\},
\ j=1,\dots,N\}.\end{equation*}
Let \label{thetaz}$\Theta(z)=\{\theta(\tau,z)\ |\
\tau\in\sss^+\}$, $z\in \{K_j, L_j, P_j, R_j\}$. Finally the union
of all $\Theta(\tau)$ is denoted by \label{theta}$\Theta$.

Let $\tau=[U_1\too V_1,\dots, U_k\too V_k; r\too r', l\too l']$ be
one of the rules of $\sss^+$. Let $u(z), v(z)$, $z\in \tkk$, be
the words associated with this rule as above.

Then we associate with $\tau$ the following list of
\label{mainrelations}{\em main relations}:
\begin{equation*}
\theta(\tau,z_-)\iv z(r,l)\theta(\tau,z) =
\alpha_{\tau^{-1}}(v_i)z(r',l')\alpha_{\tau^{-1}}(u_i),
\ i=1,\dots,k\label{mainrel} .\end{equation*}

Let $z\in \{K_j, L_j, P_j, R_j\}$, $j=1,\dots,N$, $a, b\in \aaa(z)$.
Then we add {\em auxiliary $\Theta$-relations}:
\begin{equation*}
\theta(\tau,z)\iv \alpha_\tau(a) \theta(\tau,z)=\alpha_{\tau^{-1}}(a)
\hbox{ if } \tau \hbox{ does not lock } the zz_+\hbox{-sector}
\label{auxtheta} \end{equation*}
\begin{equation*}
\begin{array}{ll}a x(b,\tau)a\iv = x(b,\tau)^4 & \hbox{ if } z=K_j \hbox{ or } z=L_j,\\
a\iv x(b,\tau)a=x(b,\tau)^4 & \hbox{ if } z=R_j.
\end{array}
\label{auxax} \end{equation*}


Finally let $b'$ be the ``brother" of $b$ in the alphabet
$\aaa(z_-)$ if $z=K_j$ or $z=L_j$. Then we need auxiliary
\label{kxrel}$(k,x)$-{\em relations}:
\begin{equation*}
\begin{array}{ll} z(r,i) x(b,\tau)=x(b',\tau)z(r,i) & \hbox{ if }
z=K_j,\\
z(r,i) x(b,\tau)=x(b',\tau)^4z(r,i) & \hbox{ if }
z=L_j.\end{array} \end{equation*}


Let $\rr(\sss)$ be the set of all relations corresponding to the
set of $S$-rules $\sss^+$.

To convert $\bsss$ into a set of relations we do not need
$\xxx$-letters, but we need ``bar"-brothers of the letters from
$\Theta$. Denote this set by \label{btheta}$\bar\Theta$.
The easiest way to explain how to convert an $S$-rule of $\bsss$
to a set of relations is the following: convert it above, then add
bars to all letters, replace all letters from $\xxx$ and
from $\bigcup\bar A(z_1), z\in \{K,L,P,R\}$ by 1. Let $\rr(\bsss)$
be the set of all relations corresponding to $\bsss^+$.

Finally the group $\hhh$ is given by the set of generators
$\kkk\cup\bar\kkk\cup\aaa\cup\bar\aaa\cup\Theta\cup\bar\Theta\cup\xxx$
and the set of relations
$\rr=\rr(\sss)\cup\rr(\bsss)\cup\{\Sigma\}$.

The complete proof of Theorem \ref{main} can be found in
\cite{OScol}.

\begin{thebibliography}{OlSa02}
\label{bibl}


\bibitem[BORS]{BORS} J. C. Birget, A. Yu. Ol'shanskii, E. Rips, M. V.
Sapir. \newblock Isoperimetric functions of groups and
computational complexity of the word problem. Annals of
Mathematics, 156, 2 (2002), 467--518.



\bibitem[Cla]{Cla} C. R. J. Clapham. \nb An embedding theorem for
finitely generated groups, Proc. London. Math. Soc. (3), 17
(1967), 419--430.
\MR{36:5199}
\bibitem[Col]{Collins} Donald J. Collins. \nb Conjugacy and the
Higman embedding theorem. Word problems, II (Conf. on Decision
Problems in Algebra, Oxford, 1976), pp. 81--85, Stud. Logic
Foundations Math., 95, North-Holland, Amsterdam-New York, 1980.
\MR{81m:20051}

\bibitem[CM]{CM} D. J. Collins, C. F. Miller III. \nb  The conjugacy
problem and subgroups of finite index. Proc. London Math. Soc. (3)
34 (1977), no. 3, 535--556.
\MR{55:8187}

\bibitem[GK]{GK} A. V. Gorjaga, A. S.  Kirkinski\u\i.\ The decidability
of the conjugacy problem cannot be transferred to finite
extensions of groups. Algebra i Logika 14 (1975), no. 4,
393--406. (Russian) 
\MR{54:2813}
\bibitem[Hi]{Hi} G. Higman. Subgroups of finitely presented groups.
Proc. Roy. Soc. Ser. A, 262 (1961), 455--475.
\MR{24:A152}


\bibitem[KT]{KT} {\em Kourovka Notebook}. Unsolved Problems in Group Theory.
5th edition, Novosibirsk, 1976.



\bibitem[Mak]{Makanin} G. S. Makanin. \nb Equations in a free group.
Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6,
1199--1273, 1344; English transl., Math. USSR-Izv. 21 (1983), 546--582.
\MR{84m:20040}

\bibitem[Ma]{Ma} Yu. I. Manin. The computable and the noncomputable, 
``Sovetskoe Radio", Moscow, 1980
\MR{82i:03002}
\bibitem[Mil]{Mil} Charles F. Miller III. \nb On group-theoretic
decision problems and their classification. Annals of Mathematics
Studies, No. 68. Princeton University Press, Princeton, N.J.;
University of Tokyo Press, Tokyo, 1971.
\MR{46:9147}


\bibitem[Ol2]{Ol97} A. Yu. Ol'shanskii.
\newblock On distortion of subgroups in finitely presented groups. Mat.
Sb. 188 (1997), no. 11, 51--98; English transl., Sb. Math. 188 (1997), no. 11,
1617--1664.
\MR{99a:20038}


\bibitem[OlSa01]{talk} A. Yu. Ol'shanskii, M. V. Sapir. Length and area
functions on groups and quasi-isometric Higman embeddings.
Internat. J. Algebra Comput. 11 (2001), no. 2, 137--170.
\MR{2002b:20058}


\bibitem[OlSa02]{OScol} A. Yu. Olshanskii, M. V. Sapir. The Conjugacy
Problem and Higman Embeddings. Preprint arXiv:math.GR/0212227.




\bibitem[Rot]{Rotman} J. Rotman.
\newblock {\it An Introduction to the Theory of Groups}.
\newblock Allyn \& Bacon, third edition, 1984.
\MR{85f:20001}

\bibitem[SBR]{SBR} M. V. Sapir, J. C. Birget, E. Rips.
\newblock Isoperimetric and isodiametric functions of groups,
Annals of Mathematics, 157, 2 (2002), 345--466.



\bibitem[Va]{Va} M. K. Valiev. On polynomial reducibility of the word
problem under embedding of recursively presented groups in
finitely presented groups. Mathematical foundations of computer
science 1975 (Fourth Sympos., Mari\'ansk\'e L\'azn\v e, 1975), pp.
432--438. Lecture Notes in Comput. Sci., Vol. 32, Springer,
Berlin, 1975.
\MR{54:413}
\end{thebibliography}

\end{document}