The
word problem for groups was first considered by Dehn [Deh11] and
Thue [Thu14], which is
to decide, when given a group 
and words 
,
whether 
is equivalent to 
in .
Novikov [Nov55] and Boone [Boo59] proved
that
there exists a finitely presented group with an
unsolvable word problem.
A finite presentation of a group consists of a set of generators (abstract
symbols) and
a set of relations that relate the freely generated words.
To be precise,
let 
be a finite set. The free group 
is a group including all elements
that can be uniquely written as a reduced
word in the form 
, where 
, 
for 
o
r 
,
and no appears adjacent to . When 
, we get
the empty word 
, which is the identity of the group.
A word is positive if it does not contain negative components. The empty
word is regarded as a positive word.
Positive words are also called strings.
Words are multiplied by
juxtaposing with all expressions 
and 
canceled
out until a reduced word is obtained. For each word 
, the inverse
word 
consists of all the symbols of written in reverse order,
where each is replaced by and each 
is replaced
by .
A relation on is an expression 
, where 
and 
are
words on .
Let 
be a finite set of relations on .
Let 
denote the normal subgroup of generated by
the 
for 
.
A group has a set of generators and a set of relations on
if is isomorphic to the
quotient group 
. and form a finite presentation of
, denoted by 
. We extend the
notation to allow several generators or sets of generators
before the semicolon and several relations
or sets of relations after the
semicolon.
A quantifier may also
be used to describe several similar relations in a compressed form.
For instance, 
represents
relations 
for 
.
In this case, we say that for a given 
is a relation
specified by the quantified statement . For simplicity, we use the term ``quantified
relation'' for such a quantified statement.
Suppose is a relation, then
, 
, 
, and 
are
called relators. Obviously, if 
is a generator, then
and 
are
relators. Let 
and 
be (not necessarily reduced) words.
Then 
means that and have exactly the same spelling.
Following Tietze transformation theorem, Wang [Wan95a]
defined the following elementary Tietze transformations for finitely
presented group
, denoted by 
, where is a symmetric operation.
Let be a word and be a relator.
(1) If is an empty word, then 
.
(2) If is not empty and has spelling 
(
or 
could be possibly null), then
.
Informally, this means that an equivalent word can be obtained by eliminating or introducing relators at any point of the original word. For simplicity, the following transformations is also considered to be elementary since such a transformation can be obtained by applying elementary transformations twice.
, 
( and could be possibly null), and
is a relation, then 
and
.
The subscript is often omitted from when there is no
confusion. Let 
.
We use 
to denote 
for some
.
Let and be two words. can be obtained from in
in 
steps if there is a sequence of elementary Tietze transformations
such that
in .
For a presentation , we assume
that words over and relations (with or without quantifiers)
in are properly coded as binary strings.
Wang [Wan95a]
studied the following distributional word problem for finitely
presented groups, which is a slight modification of the original
word problem of Dehn and Thue.
DISTRIBUTIONAL WORD PROBLEM FOR FINITELY PRESENTED
GROUPS
Instance. A finitely presented group 
, binary strings
, and a positive integer , where
consists of generators and
consists of
relations (with or without quantifiers), all coded in binary form.
The size of the instance is 
.
Question. Is 
in for
? (
is called a conjugation of on , denote
d by
.)
Distribution. Randomly and independently select positive integers 
,
, , and binary strings , , and . Then randomly and independently
choose binary strings 
and 
. The random choices
are made with respect to the default uniform probability distributions
on positive integers and binary strings. Hence, the probability
distribution is proportional to
The distributional word problem for finitely presented groups was shown to be average-case NP-complete by Wang [Wan95a].
