The distributional word problem for finitely presented groups
was shown to be complete for DistNP by Wang [Wan95a].
The idea of proving this result is as follows. Given a randomized
NP decision problem 
, we construct
a reduction such that for any instance 
of 
, the reduction
transforms to a finitely presented group 
, strings 
,
and a unary notation for 
with the following properties, where 
is a fixed polynomial.
is equivalent to 
in 
iff
in for 
iff 
.
is dominated by the default uniform
distribution of the word
problem with respect to the reduction.
Proof.simplicity,
we again use the
standard nondeterministic one-tape
single-headed Turing machines
as our computation model as in the proof of Theorem 5.5.
Let 
be an arbitrary distributional problem in DistNP.
By the Distribution Controlling Lemma, there is a total, one-one,
p-time computable and p-time invertible function 
such that
.
Let 
be a
(nondeterministic) Turing machine that accepts in polynomial time.
Without loss of generality we assume that all the computation paths of are
bounded by a polynomial on the length of inputs.
We construct a Turing machine 
with only one halting state
exactly the same as in the proof of Theorem 5.5.
We assume that when enters an infinite loop, it
does not change anything on the tape.
Then
for all , on input 
has a halting computation
if and only if accepts .
Because of the time bound on ,
it is easy to see that if on input halts, then the
number of steps
it takes is
bounded by a polynomial on 
. So we have
We construct a set 
of productions
to describe
instantaneous descriptions of exactly the same as
in the proof of Theorem 5.5.
We now construct a Thue
system 
based on 
, which is
somewhat different from that in the proof of Theorem 5.5.
We first construct a new set of symbols 
and a disjoint
new set of states
. We want 
to contain productions only in the form of
, where 
are states in , and
are
strings on .
In so doing,
our job will become relatively easier when
constructing a finitely presented group that meets our needs.
Since is finite,
we can fix an order 
for the ordered pairs in . We use new symbols 
, 
to handle nondeterminism in case the inverse of
a production
is applied.
We use two extra states 
and 
to transform input to
its coded form before the actual simulation of on begins.
We use another two extra states 
and a set of new symbols
as markers
to move around when needed. Let
will contain 
productions,
which will be described later.
We then
construct a finitely presented group 
based on .
Let 
be a new set defined below.
Some extra symbols are needed for writing quantified relations.
Let 
be a finite alphabet
distinct from
which is sufficient to describe quantified statements. For instance,
may contain quantifier symbols, relational operation symbols, and
variable symbols, etc.
Let 
.
Fix a dynamic binary coding scheme for 
and the finite
set
The length of any coded symbol is
.
For any positive word 
on 
, we use
to denote the coded word of .
Let 
.
The string-rewriting system
consists of the following productions:
1:
:
2:
:
, where 
3:
:
4:
Proof.that starting from string
, the only productions
that can be applied are the ones in 1 starting with the first
one until is transformed
to 
.
Because of the coding
scheme we use
this transformation can be done without miscoding the already coded strings.
Since can be uniquely
written as 
, where 
,
this transformation can be carried out
in 
steps.
Assume that halts on in polynomial time 
.
Using the rules in 2, which duplicate the steps of
that halts on ,
and using the rules in 3 as necessary,
can be transformed into
.
After each application of a 2 rule, it will be necessary to apply
at most 
3 rules to move the symbol 
as far left as possible.
So transforming into
will take at most
steps.
Finally,
can be transformed into 
in 
steps by 4 rules.
Conversely, if can be transformed
into , then will halt on . It is important to
note that the inverse of a production in can undo a simulated
step of , but since each simulated step is kept track of through
the 's using the 2 rules, it can only bring the
string back to a previous simulated ID of .
Letting 
completes the proof.
We now construct a finitely presented group .
The set of generators of is
The symbols 
and 
are used to represent negative
and power words.
The symbols in are used to
represent quantified relations. We assume that all
integers are written in the original binary form
(i.e., not coded in the dynamic coding scheme).
Recall that each coded symbol
is a string of the form 
. We code a positive
binary integer
by replacing 1 with 10, 0 with 01. A binary number so coded is easily
distinguished from any coded symbol in . Let 
denote
such a coded binary number.
We will use
words of the form 
in
constructing group relations. Although it is exponential to
write such a word as a direct concatenation of symbol 
, it can be
represented in a much compressed form without affecting the actual
group operations. We represent negative words and power words
as follows.
is coded by 
,
denoted as , where 
is positive.
is also denoted as 
.
is coded by 
,
denoted as , where 
,
and 
.
is coded by 
,
denoted as , where is positive.
is coded by 
, denoted as .
is coded by 
,
denoted as , where ,
and .
This coding scheme
provides
a much shorter
representation for power words. For instance,
the length of is 
.
Notice that this is only a representation of power words
and so it does not
introduce new generating symbols or relations.
For any word on , we use to denote
the coded word of .
One can easily define operations
for the power words so coded following the standard rules such that,
for example,
,
,
.
These operations
can be carried out in polynomial time in terms of 
, the
length of 
, and the length of .
Let 
be a word. Then 
is coded as
above by replacing with 
,
denoted as , where 
.
If 
is a coded word already, then
is coded as above by replacing with
.
Group operations can be applied on this representation in a
natural way. For example, 
,
,
where and 
are coded words.
Let and 
be variables, we write 
to denote the concatenation of 
for times. Symbolically,
is written as 
and
is written as 
. When is substituted with
an actual value, the rules above are followed.
We now define a finite set of relations 
to construct a finite presentation of group
.
Fix an order for the rewriting rules in .
Suppose 
is a (not necessarily positive) word, then
.
consists of the following relations:
:
: 
.
:
and 
:
.
:
, if
is the 
-th relation
in in the fixed
order. Here and 
are states in .
:
:
:
be a variable representing positive words on ,
let 
be a variable representing
.
For all with length 
and for all 
:
It is easy to see that contains finitely many relations.
The number of relations and the number of quantified relations
are independent
of .
The length of each relation except for is independent of .
For the quantified relations in , the only thing that depends on
is the value of 
. Anything else can be symbolically
written down as the way it is in our coding system (i.e.,
without further evaluations). The
length of each relation is therefore 
.
(We can also see that each relation (without quantifier)
specified in has length 
in our coding system.)
We will now show that halts on input iff
in with 
a fixed polynomial.
Proof.that 
in
with 
. Then
and each 
is bounded by 
for a fixed constant
.
Suppose 
by applying a rewriting rule ,
then either
and 
, or
and 
,
where
and 
are positive words on .
Let be of the form
, where and are words on and 
.
Then write 
to denote 
.
Now in 
, using one relation in and two relations
specified in 
, we have
where 
and 
.
It is easy to see
that 
and 
in the way
the power strings are coded.
So we have
One can
similarly obtain the same result if and , where
and
.
So we have
where 
.
Similarly, we can show that 
in .
Using a polynomial number of relations in and (2) of ,
we have
So 
in
for 
, where
is some fixed polynomial.
This completes the proof.
From Lemmas 5.8, 5.9, and 5.10, we have
We use Higman-Neumann-Neumann (HNN) extensions to prove the
other direction.
We first point out that the relations specified in can be derived
from other relations in using elementary Tietze transformations.
Proof.need only to demonstrate how to obtain 
using relations not in , where
is a positive word. The
others can be similarly obtained. We prove it by induction on 
.
The case of 
is obvious. For the general case, let 
,
where 
, then
,
where 
. Keep using relations in and
we have
.
This completes the proof.
Hence, two words being equivalent in group using relations specified in
for polynomially many times implies that
these two words are equivalent in group without relations specified
in ,
but they may require using exponentially many other relations.
What we are interested here
is that as long as 
is
equivalent to 
in ,
without using the redundant relations in ,
we will have 
in .
Then using Lemmas 5.8 and 5.9 we will get what we want.
By the way we built in which every relation is in the form
, where are states in , and
are
strings on , the proof given in Rotman [Rot88] can be used in
exactly the same way to prove our result here. In particular, our
proof is simpler as we need only to consider a special case.
We outline the proof below and
the reader is referred to [Rot88] for more details.
We first show that the group is the end result of a chain of
HNN extensions. 
Let 
be a set. Write 
for 
.
Let 
.
Define groups 
, 
,
, and 
as follows:
Clearly, we can assume that both 
and 
are reduced words.
A word is -reduced if it contains no sub-words of the form
or 
.
By combining all these lemmas we finally get
Now we are ready to finish the proof of Theorem 5.7.
We define a reduction 
as follows:
Clearly, is one-to-one.
As shown earlier, 
contains constant number of symbols depending on
and contains constant number of relations (some with
quantifiers). The
length of each coded symbol and the length of each of these
relations are . So
the probability distribution of 
is proportional to
for a polynomial 
which dominates 
.
This completes the proof of Theorem 5.7.
