In 1961, G. Higman [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 [Nov] and Boone
[Bo] this result showed that objects from logic (in that case, recursively
enumerable sets) have group theoretic characterizations (see Manin [Ma] for
the philosophy of Higman embeddings).
Clapham [Cla] (see also corrections in [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 [Va] sketched a proof of a much stronger result: ev-
ery finitely generated recursively presented group G embeds in a finitely
presented group H such that the word problem in H polynomially reduces
to the word problem in G. In particular, if the word problem of a finitely
generated group is in P (i.e. can be solved in polynomial time by a deter-
ministic Turing machine) then it can be embedded into a finitely presented
group whose word problem is also in P (a correction to Valiev's paper was
published in Mathematical reviews, review 54 # 413, see also Lyndon and
Schupp [LS] and Manin [Ma]). A simplified version of Valiev's construction
(but not a proof of the polynomial reducibility) was later published by Aan-
deraa and Cohen in [AC] (see also Kalorkoti [Kal]). In [BORS], Birget, Rips
and the authors of this paper obtained a group theoretic characterization of
NP (non-deterministic 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 un-
der embeddings. Collins and Miller [CM] and Gorjaga and Kirkinskii[GK]
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 [KT] posed the following question (problem 5.22):
Does there exist a version of the Higman embedding theorem in which the
degree of unsolvability of the conjugacy problem is preserved?
Received by the editor November 21, 2002.
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
99-01-00894 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.