These pages are not updated anymore. They reflect the state of . 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}