text:
\section{Introduction}

\subsection{Background}

Suppose that $G$ is a finitely generated group.
Let $\Sigma$ be a finite generating set which is \emph{symmetric}:
if $a$ lies in $\Sigma$ then so does $a^{-1}$.
The \emph{word problem} for $G$ asks whether a given word $w \in \Sigma^*$ represents the identity in $G$.
This, along with the \emph{conjugacy} and \emph{isomorphism problems}, were set out by Dehn~\cite{Dehn11} in 1911.
These three decision problems are now recognized as being fundamental in group theory generally.

However, Dehn's claimed justification was that he could use solutions to these problems to solve further problems in what is now called \emph{low-dimensional topology}.
Dehn's techniques, in particular his solution to the word problem in surface groups, were greatly generalized by Gromov.
In~\cite{Gro87} Gromov introduced what are now called \emph{word-hyperbolic} or \emph{Gromov hyperbolic} groups.
(We will simply call these \emph{hyperbolic} groups.
See Section~\ref{sec-hyp} for definitions.)
With this and other innovations Gromov revived the strictly geometric study of groups.  For example, he characterized hyperbolic groups as being exactly those that satisfy a linear isoperimetric inequality.  Gromov also showed that, in certain models of \emph{random groups}, all groups are (almost surely) hyperbolic~\cite{Gro87, Olsh92}.

Another theme in geometric group theory is the subject of \emph{distortion}.
As a concrete example, consider the Baumslag-Solitar group $G = \group{a, b}{ b^{-1} a b = a^2 }$.
The subgroup $\subgp{a}$ is exponentially distorted in $G$, in the sense that the element $a^{2^n} =_G b^{-n} a b^n$ has length $2^n$ as an element of $\subgp{a}$ but length $2n + 1$ as an element of $G$.
Thus, to solve the word problem efficiently in $G$ it seems necessary to record exponents of $a$, say in binary; see also \cite{Weiss16}.

So, seeking to solve the word problem in groups leads us to consider \emph{compressed words}: elements of the group given via some useful succinct representation.
One popular such representation is via \emph{straight-line programs};
we give definitions and examples in Section~\ref{sec-SLP-def}.
We will call the word problem for such the \emph{compressed word problem}.

The motivating result for this paper is a theorem due to the second author~\cite{Loh06siam}.
Let $F_n$ be the free group on $n$ generators.
Lohrey gives a polynomial-time algorithm to solve the compressed word problem for $F_n$; in fact this problem is $\Ptime$--complete.
Building on this, the third author shows in~\cite{Schl06} that the word problems for $\Aut(F_n)$ and $\Out(F_n)$ can be solved in polynomial time.
Schleimer goes on to show that the compressed word problem for closed surface groups is polynomial time.
This also gives a new solution to the word problem in mapping class groups of surfaces.

This sequence of results closely parallels Dehn's original development, but in the compressed setting.

\subsection{This paper}

Suppose that $w$ is a word in the generators of $G$.
We say $w$ is \emph{shortlex reduced} if it is shorter than (or of the same length and lexicographically earlier than) any other word representing the same group element; see Definition~\ref{def-shortlex}.
Suppose that ${\mathcal{G}}$ is a straight-line program over $\Sigma$.
Then we denote the output of ${\mathcal{G}}$ by $\mathsf{eval}({\mathcal{G}})$.
Here is our main result\footnote{This was previously announced without proof: see \cite[Theorem~4.12]{Loh14}.}.

\begin{restate}{Theorem}{thm-SLP-for-shortlex}
Let $G$ be a hyperbolic group, with symmetric generating set $\Sigma$.
There is a polynomial-time algorithm that, given a straight-line program ${\mathcal{G}}$ over $\Sigma$, finds a straight-line program ${\mathcal{H}}$ so that $\mathsf{eval}({\mathcal{H}})$ is the shortlex reduction of $\mathsf{eval}({\mathcal{G}})$.
\end{restate}

From this we deduce the following.

\begin{restate}{Corollary}{coro-CWP-hyperbolic}
Let $G$ be a hyperbolic group.
Then the compressed word problem for $G$ can be solved in polynomial time.
\end{restate}

\subsection{Applications}

Given these results, in Section~\ref{sec-conjugacy} we deal with the compressed versions of several other algorithmic problems.
Recall that the \emph{order problem} for a group $G$ asks us, given an element $g \in G$, to compute the order of $g$.  Since hyperbolic groups only have torsion elements of bounded order we can prove the following.

\begin{restate}{Corollary}{coro-order}
Let $G$ be a hyperbolic group.
Then the compressed order problem for $G$ can be solved in polynomial time.
\end{restate}

The first author, with Epstein, proved in~\cite{EpsteinH06} that the conjugacy problem in hyperbolic groups is linear time.

If, in the conjugacy problem, we replace the given pair of elements by a pair of finite ordered lists of elements then we obtain the \emph{simultaneous conjugacy problem}.
See~\cite{KaMa12} and its references for a discussion of this problem, for various classes of groups.

The \emph{centralizer problem} asks for the centralizer of a given finitely generated subgroup of $G$.
The first author, with Buckley, proved in~\cite{BuckleyHolt13} that the simultaneous conjugacy problem as well as the centralizer problem for hyperbolic groups is linear time.

Using the results of~\cite{EpsteinH06, BuckleyHolt13}, and our work above, we solve the compressed versions of these problems.

\begin{restate}{Theorem}{thm-compcp}
Let $G$ be a hyperbolic group.
Then the compressed simultaneous conjugacy problem for $G$ can be solved in polynomial time.
Moreover, if the two input lists are conjugate, then we can compute a straight-line program for a conjugating element in polynomial time.
\end{restate}

\begin{restate}{Theorem}{thm-comp-central}
Let $G$ be a hyperbolic group.
Then the compressed centralizer problem for $G$ can be solved in polynomial time.
\end{restate}

We remark that, for finitely generated nilpotent groups, the (compressed) simultaneous conjugacy problem is solvable in polynomial time~\cite[Theorem~7]{MacDonaldMO17}.

As suggested in~\cite{Schl06}, the word problem for a finitely generated subgroup of the automorphism group $\Aut(G)$ is polynomial-time reducible to the compressed word problem for $G$.
Similarly, the word problem for a finitely generated subgroup of the outer automorphism group $\Out(G)$ is polynomial-time reducible to the compressed simultaneous conjugacy problem for $G$; see~\cite[Proposition~10]{HauLohHau13}.

Note that, if $G$ is hyperbolic then $\Aut(G)$, and thus $\Out(G)$, are finitely generated: see~\cite{DaGui11}.
We deduce the following.

\begin{corollary}
Let $G$ be a hyperbolic group.
Then the word problems for $\Aut(G)$ and $\Out(G)$ can be solved in polynomial time.
\end{corollary}

Our final application is to knapsack problems.
Suppose that $G$ is a finitely generated group.
The given input is a list $(u, u_1, u_2, \ldots, u_k)$ of words over the generators of $G$.
We are asked if there are natural numbers $n_1, n_2, \ldots, n_k$ such that
\[
u =_G u_1^{n_1} u_2^{n_2} \cdots u_k^{n_k}
\]
When $G$ is hyperbolic, the knapsack problem can be solved in polynomial time; see~\cite[Theorem~6.1]{MyNiUs14}.

In the compressed knapsack problem, the words $u, u_1, u_2, \ldots, u_k$ are represented by straight-line programs.
For the special case $G = \mathbb{Z}$ this problem is a variant of the classical knapsack problem for binary encoded integers, which is known to be $\NP$--complete.
Using this, and our results above, we prove the following.

\begin{restate}{Theorem}{thm-knapsack-hyp}
Let $G$ be an infinite hyperbolic group.
Then the compressed knapsack problem for $G$ is $\NP$--complete.
\end{restate}

\subsection{Related work}

We here give a brief overview of previous work.  For a more in-depth treatment, we refer to~\cite{Loh12survey, Loh14}.

\subsubsection{Compressed word problems}
The use of straight-line programs in group theory dates back to, at least, the methods developed by Sims~\cite{Sims70} for computing with a subgroup of the symmetric group $S_n$ defined by generators.
The first step in virtually all of the algorithms developed by Sims is to expand the given list of generators to a longer list (a \emph{strong generating set}) by defining a sequence of new generators as words in the existing generators.
Straight-line programs were later used, again in the context of finite groups, by Babai and Szemeredi~\cite{BabSzem84} in the proof of the \emph{Reachability Theorem}.

Note that the compressed word problem for a group $G$ is decidable if and only if the word problem for $G$ is decidable.
However, the computational complexity of the compressed word problem for $G$ can be strictly more difficult than the word problem itself.  We return to this topic below.

It is interesting to note that the compressed word problem for a group $G$ is exactly the \emph{circuit evaluation problem} for $G$.
For finite groups the compressed word problem, and thus the circuit evaluation problem, is linear time.
In fact, more is known.
The parallel complexity of the circuit evaluation problem over finite groups is investigated in~\cite{BeMcPeTh97}.
If $G$ is a finite solvable group, then the compressed word problem for $G$ belongs to the parallel complexity class $\DET \subseteq \NC^2$.
If $G$ is finite and not solvable, then the compressed word problem for $G$ is $\Ptime$--complete.

We now turn our attention to infinite, but finitely generated, groups.
As mentioned above, the word problem for a finitely generated subgroup of $\Aut(G)$ is polynomial-time reducible to the compressed word problem for $G$.
A similar reduction exists for certain group extensions~\cite[Theorem~4.8 and 4.9]{Loh14}.
These results on automorphisms are tightly connected to the study of distortion of subgroups, mentioned above.

Beyond hyperbolic groups, there are several important classes of groups where the compressed word problem can be solved in polynomial time.  These include the following.
\begin{itemize}
\item
Finitely generated nilpotent groups~\cite[Section~4.7]{Loh14}.
Here, the compressed word problem belongs to the parallel complexity class $\DET$~\cite{KonigL15}.
\item
Virtually special groups; that is, finite extensions of finitely generated subgroups of right-angled Artin groups~\cite[Corollary~5.6]{Loh14}.
Right-angled Artin groups are also known as graph groups or partially commutative groups.
This class contains all Coxeter groups~\cite{HagWi10}, one-relator groups with torsion~\cite{Wis09}, fully residually free groups~\cite{Wis09}, and fundamental groups of hyperbolic three-manifolds~\cite{Agol13}.
Note that the case of fully residually free groups is independently due to Macdonald~\cite{Macd09}.
\end{itemize}

Furthermore, the class of groups with polynomial time compressed word problem is closed under the following operations.
\begin{itemize}
\item
Graph products~\cite[Chapter~5]{Loh14}.
\item
Amalgamated free products (or HNN extensions) where the edges groups are finite~\cite[Chapter~6]{Loh14}.
\end{itemize}

We also note that, for finitely generated linear groups, the compressed word problem belongs to the complexity class $\coRP$~\cite[Theorem~4.15]{Loh14}.
That is, there is a randomized polynomial-time algorithm that may err with a small probability on negative input instances.

\subsubsection{Hardness results}
Certain hardness results for the compressed word problems have also been obtained.
\begin{itemize}
\item
The compressed word problem for every restricted wreath product $G \wr \mathbb{Z}$ with $G$ finitely generated nonabelian is $\coNP$--hard~\cite[Theorem~4.21]{Loh14}.
An even stronger but somewhat technical hardness result can be found in \cite{BartholdiFLW19}. In the latter paper it is also shown that the compressed word problem is $\PSPACE$-complete
for several famous groups including Thompson's group $F$, the Grigorchuk group and the Gupta-Sidki groups.
The word problem for the Grigorchuk group can be solved in logarithmic space \cite{GaZa91}.
This yields an example of a group where the compressed word problem is provably more difficult than the word problem.
\item
There exist automaton groups with an $\EXPSPACE$--complete compressed word problem~\cite{WaeWei19}.  On the other hand, the uncompressed word problem for any automaton group belongs to $\PSPACE$.
\item
The compressed word problem for the linear group $\SL(3, \mathbb{Z})$ is equivalent, up to polynomial-time reductions, to the problem of \emph{polynomial identity testing}.
This last is the decision problem of whether a given circuit over the polynomial ring $\mathbb{Z}[x_1, \ldots, x_n]$ evaluates to the zero polynomial~\cite[Theorem~4.16]{Loh14}.
The existence of a polynomial-time algorithm for  polynomial identity testing is an outstanding open problem in the area of algebraic complexity theory.
\end{itemize}

\subsubsection{Knapsack problems over groups}
The uncompressed knapsack problem has been studied for various classes of groups; see~\cite{FrenkelNU15, GanardiKLZ18, KoenigLohreyZetzsche2015a}.
For non-elementary hyperbolic groups, the knapsack problem lies in $\LogCFL$ (the logspace closure of the class of context-free languages); see~\cite{Loh2019}.
The second author shows, in~\cite{LohreyZ18}, that the compressed knapsack problem for every virtually special group belongs to $\NP$.

\subsubsection{Compressing integers}
In addition to straight-line programs, there are other methods of compression that arise in significant ways in computational group theory.
Here we will mention just a few with particular relevance to the word problem.
These are techniques for recording extremely large integers, as opposed to recording long words.

The binary representation of an integer $n$ can be translated into a straight-line program ${\mathcal{G}}_n$ of size $\mathcal{O}(\log n)$ with output $a^n$.
Following our discussion of circuit evaluation above, we could replace ``concatenation of strings'' by the primitive operator ``addition of integers''.  Likewise, we replace the alphabet $\{a\}$ by the alphabet $\{1\}$.  This transforms the straight-line program ${\mathcal{G}}_n$ into an additive circuit with output $n$.

If we allow multiplication as well as addition gates we obtain \emph{arithmetic circuits}.
For example, a circuit with $n$ gates can produce an integer of size $2^{2^n}$ using iterated squaring.
\emph{Power circuits}, the topic of~\cite{MyUsWo}, replace multiplication of $x$ and $y$ by the operation $x \cdot 2^y$:
that is, shifting the first input by the second.
Thus a power circuit of depth $n$ can represent an integer of the size of a tower of exponentials of height $n$.
The same authors use their new theory, in~\cite{MyUsWo11}, to show that the word problem in Baumslag's group~\cite{Baumslag69}
\[
\group{a, b \,}{ \left( b^{-1} a b \right)^{-1} a \left( b^{-1} a b \right) = a^2 }
\]
is polynomial time.
We note that Baumslag's group has a non-elementary Dehn function \cite{Plat04};
this demonstrates one of the many posible separations between the computational and the geometric theories of a group.

Again exploiting various properties of power circuits, the authors of~\cite{DiekertLU12} give a cubic time algorithm for the word problem in Baumslag's group.  They also show that the word problem for Higman's group~\cite{Higman51}
\[
\group{a, b, c, d}{ b^{-1}ab = a^2, c^{-1}bc = b^2, d^{-1}cd = c^2, a^{-1}da = d^2 }
\]
is polynomial time.

Of course, even more extreme compression is possible and this, surprisingly, leads to polynomial-time algorithms for even more extreme groups.  The authors of \cite{DisonER16, DisonER18} use Ackermann functions; they show that the word problems for the \emph{hydra groups}~\cite{DisonRiley13}
\[
H_k = \group{a, b}{ [ \cdot \! \cdot \! \cdot [[a, b], b], \ldots , b] = 1 }
\]
are polynomial time.
Here $[x, y] = x^{-1} y^{-1} x y$ is a \emph{commutator};
the relation in $H_k$ is a nested commutator of depth $k$.

\subsection{Acknowledgements}
An extended abstract of this paper appeared in \cite{HoltLS19}.
The third author thanks the first two for their patience during the writing of this paper.

\section{General notation}
\label{sec-notation}

We include zero in the set of natural numbers; that is, $\mathbb{N} = \{0, 1, 2, \ldots \}$.

\subsection{Words}

Suppose that $\Sigma$ is an \emph{alphabet}; the elements of $\Sigma$ are called \emph{letters}.
We write $\Sigma^*$ for the \emph{Kleene closure} of $\Sigma$; that is, the set of all finite words over $\Sigma$.
We call any subset $L \subseteq \Sigma^*$ a \emph{language} over $\Sigma$.

For any alphabet $\Sigma$, we use $\varepsilon \in \Sigma^*$ to denote the \emph{empty word}.
Suppose that $u$, $v$, and $w$ are words over $\Sigma$.
We denote the \emph{concatenation} of $u$ and $v$ by $u \cdot v$; we often simplify this to just $uv$.
So, for example, $w \cdot \varepsilon = \varepsilon \cdot w = w$.
We say that $u$ is a \emph{factor} of $v$ if there are words $x$ and $y$ so that $v = xuy$.
We say that $u$ is a \emph{rotation} of $v$ if there are words $x$ and $y$ so that $v = x y$ and $u = y x$.
We have the following easy but useful result.

\begin{lemma}
\label{lem-rotation}
Let $u$ and $v$ be words over $\Sigma$.
Then $u$ is a rotation of $v$ if and only if $|u| = |v|$ and $u$ is a factor of $v \cdot v$.
\qed
\end{lemma}

Suppose that $w = a_0 \cdot a_1 \cdots a_{n-1}$ lies in $\Sigma^*$, where the $a_i$ are letters.
Then we define $|w|$ to be the \emph{length} of $w$; that is, $|w| = n$.
For any $i$ between zero and $n-1$ (inclusive) we define $w[i] = a_i$.
Note that the empty word $\varepsilon$ is the unique word of length zero.

We now define the \emph{cut operators}.
Let $w$ be a word, as above, and let $i$ and $j$ be indices, as above, with $i \leq j$.
We define $w[i:j] = a_i \cdots a_{j-1}$.
We use $w[:j]$ to denote $w[0:j]$, the \emph{prefix} of length $j$.
We use $w[i:]$ to denote $w[i:n]$, the \emph{suffix} of length $n - i$.
Note that $w[i:i] = \varepsilon$ and $w = w[:i] \cdot w[i:]$.

Suppose that $\Sigma$ is a finite alphabet equipped with a total order $<$.

\begin{definition}
\label{def-shortlex}
We define the \emph{shortlex order} on $\Sigma^*$ as follows.  For words $u, v$ we have $u <_\mathsf{slex} v$ if
\begin{itemize}
\item
$|u| < |v|$ or
\item
$|u| = |v|$ and there are words $x, y, z \in \Sigma^*$ and letters $a, b \in \Sigma$ so that
\begin{itemize}
\item
$u = xay$,
\item
$v = xbz$, and
\item
$a < b$.
\end{itemize}
\end{itemize}
\end{definition}

Note that shortlex is a \emph{well-order} on $\Sigma^*$: that is, every nonempty subset of $\Sigma^*$ has a unique shortlex least element.

\subsection{Finite state automata}

We refer to~\cite{HoUl79} for background in automata theory.
A \emph{(deterministic) finite state automaton} is a tuple $M = (Q, \Sigma, q_0, \delta, F)$, where
\begin{itemize}
\item
$Q$ is a finite set of \emph{states},
\item
$\Sigma$ is a finite alphabet,
\item
$q_0 \in Q$ is the \emph{initial} state,
\item
$\delta \colon Q \times \Sigma \to Q$ is a \emph{transition} function, and
\item
$F \subseteq Q$ is the set of \emph{accept} states.
\end{itemize}

Intuitively, if the automaton $M$ is ``in'' state $q \in Q$, and receives input $a \in \Sigma$, then it transitions to the new state $\delta(q,a)$.
We extend $\delta$ to a function $\delta' \colon Q \times \Sigma^* \to Q$ recursively.  That is, for any state $q$, word $w$, and letter $a$ we have
\begin{itemize}
\item
$\delta'(q, \varepsilon) = q$ and
\item
$\delta'(q, wa) = \delta( \delta'(q, w), a)$.
\end{itemize}
Since $\delta$ and $\delta'$ agree on words of length at most one, we will suppress $\delta'$ in what follows and instead reuse $\delta$.
We define
\[
L(M) = \{ w \in \Sigma^* \st \delta(q_0, w) \in F \}
\]
to be the language \emph{accepted} by $M$.
Intuitively, if $w$ lies in $L(M)$ then $w$, when input into $M$, takes it from the initial state to an accept state.

We say that a language $L \subseteq \Sigma^*$ is \emph{regular} if there exists a finite state automaton $M$ so that $L = L(M)$.

\section{Hyperbolic groups}
\label{sec-hyp}

We refer to~\cite{ABCFLMSS91} as a general reference on (word) hyperbolic groups.

Let $G$ be a finitely generated group.
Let $1_G$ denote the identity element of $G$.
Let $\Sigma$ be a finite, \emph{symmetric} generating set for $G$.
That is, if $a$ lies in $\Sigma$ then so does $a^{-1}$.
For two words $u, v \in \Sigma^*$, we will use $u =_G v$ to mean that $u$ and $v$ represent the same element of $G$.

The \emph{(right) Cayley graph} $\Gamma = \Gamma(G, \Sigma)$ of $G$ with respect to $\Sigma$ is defined as follows.
\begin{itemize}
\item
The vertices of $\Gamma$ are the elements of $G$.
\item
The undirected edges of $\Gamma$ are of the form $\{g, ga\}$ for $g \in G$ and $a \in \Sigma$.
\end{itemize}
We will label a directed edge $(g, ga)$ with the letter $a$.
Note that $G$ acts, via group automorphisms, on $\Gamma$ on the left.

Giving all edges length one makes $\Gamma$ into a geodesic metric space.
We do this in such a way so the action of $G$ is now by isometries.
The distance between two points $p, q$ is denoted $d_\Gamma(p, q)$.
For $g \in G$ we define $|g| = d_\Gamma(1,g)$.
We deduce that $|g|$ is the smallest length among all words $w \in \Sigma^*$ that represent $g$.
Fix $r \geq 0$.  The ball of radius $r$ in $\Gamma$ is the set
\[
{\sf{Ball}}(r) = {\sf{Ball}}_\Gamma(r) = \{ g \in G : |g| \leq r \}
\]

Fix a word $w \in \Sigma^*$.
We define $P_w \subseteq \Gamma$ to be the path starting $1_G$ which is labelled by $w$.
Thus the path $g \cdot P_w$ starts at $g$ and is again labelled by $w$.
In general, we will take $P \colon [0, n] \to \Gamma$ to be an edge path from $P(0)$ to $P(n)$.
In particular, we must allow real $t \in [0, n]$ as we traverse edges.
We use $\bar{P}$ to denote $P$ with its parametrization reversed.
Note that $\bar{P}_w = g_w P_{w^{-1}}$.

We call a path $P$ \emph{geodesic} if for all real $t$ we have $d_\Gamma(P(0), P(t)) = t$.
Suppose that the word $w \in \Sigma^*$ represents the group element $g_w \in G$.
We say that $w \in \Sigma^*$ is \emph{geodesic} if the path $P_w$ is geodesic.
We say that $w \in \Sigma^*$ is \emph{shortlex reduced} if for all $u \in \Sigma^*$ the equality $g_u = g_w$ implies $w \leq_\mathsf{slex} u$.
We use $\mathsf{slex}(w)$ to denote the shortlex reduced representative of $g_w$.

\begin{remark*}
Suppose that $w$ is geodesic or shortlex reduced.
Suppose that $u$ is a factor of $w$.
Then $u$ is also, respectively, geodesic or shortlex reduced.
\end{remark*}

A \emph{geodesic triangle} consists of three \emph{vertices} $p, q, r \in G$ and three \emph{sides} $P, Q, R \subset \Gamma$.
The sides are geodesic paths connecting the vertices; see Figure~\ref{fig-triangle}.
Fix $\delta \geq 0$.
We now follow~\cite[Definition~1.3]{ABCFLMSS91}.
We say a geodesic triangle is \emph{$\delta$--slim} for every point $x$ in the side $P$ is distance at most $\delta$ from some point of $R \cup Q$, and similarly for the sides $Q$ and $R$.

Fix $G$ and $\Sigma$ as above.
We say $G$ is \emph{$\delta$--hyperbolic} if  every geodesic triangle in the Cayley graph $\Gamma = \Gamma(G, \Sigma)$ is $\delta$--slim.
Finally, we simply say $G$ is \emph{hyperbolic}, if it is  $\delta$--hyperbolic for some $\delta \geq 0$.
For example, the group $G$ is $0$--hyperbolic (with respect to $\Sigma$) if and only if $G$ is a free group, freely generated by (half of) $\Sigma$.

\begin{remark}
\label{rem-gromov}
In his article~\cite{Gro87}, Gromov proved that hyperbolic groups have many good properties.  In Corollary~2.3.B he states that such groups satisfy a linear isoperimetric inequality; hence they have solvable word problem.  In Corollary 2.3.E he shows that the notion of hyperbolicity is independent of the choice of finite generating set.  In Section 7.4.B he proves that they have solvable conjugacy problem.  For another exposition of these results (excepting the conjugacy problem) we refer to~\cite{ABCFLMSS91}: see Theorem~2.5, Proposition~2.10, and Theorem~2.18 of that work.  For an exposition of the conjugacy problem we refer to~\cite{EpsteinH06}.
\end{remark}

We will need a seemingly stronger condition on our geodesic triangles, called \emph{$\delta$--thinness}.
We here follow~\cite[Definition~1.5]{ABCFLMSS91}.
Suppose again that we have a geodesic triangle with vertices $p, q, r \in G$ and with sides $P, Q, R \subset \Gamma$; see Figure~\ref{fig-triangle}.
Let $c_P \in P$, $c_Q \in Q$, and $c_R \in R$ be the unique points so that
\[
d_\Gamma(p, c_Q) = d_\Gamma(p, c_R), \quad d_\Gamma(q, c_R) = d_\Gamma(q, c_P), \quad d_\Gamma(r, c_P) = d_\Gamma(r, c_Q)
\]
We call these the \emph{meeting points} of the triangle.
Note that the meeting points may be elements of $G$ or midpoints of edges of $\Gamma$.
Suppose that $x \in P$ and $y \in Q$ are points with
\begin{itemize}
\item
$d_\Gamma(r, x) = d_\Gamma(r, y) = t$ and
\item
$t \leq d_\Gamma(r, c_P) = d_\Gamma(r, c_Q)$.
\end{itemize}
Then we call $x$ and $y$ \emph{corresponding points} with respect to $r$.
Note that is one of $x$ or $y$ lies in $G$ then so does the other.
We make the same definition with respect to the vertices $p$ and $q$.
Note that the three meeting points are all in correspondence.
Fix $\delta \geq 0$.
The triangle is called \emph{$\delta$--thin} if for all corresponding pairs $(x, y)$ we have $d_\Gamma(x,y) \leq \delta$.
See Figure~\ref{fig-triangle}; there the dotted arcs indicate corresponding pairs.
Note that a $\delta$--thin triangle is $\delta$--slim.
A converse also holds: every geodesic triangle in a $\delta$--hyperbolic space is $4\delta$--thin; see~\cite[Proposition 2.1]{ABCFLMSS91}.

\begin{figure}[t]
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}

        \tikzstyle{small} = [circle, draw = black, fill = black,inner sep=.25mm]
        \tikzstyle{smaller} = [circle, draw = black,fill=black,inner sep=.05mm]
        \tikzstyle{tiny} = [circle, draw = black,inner sep=.0mm]
        \tikzstyle{zero} = [circle, inner sep=0mm]

        \def185.0166{185.0166}
        \def152.72462{152.72462}
        \def164.06123{164.06123}

        \def86.84{86.84}
        \def98.1766{98.1766}
        \def65.8846{65.8846}

        \node (p) at (0,0) [small, label=left:$p$] {};
        \node (q) at (6,0) [small, label=right:$q$] {};
        \node (r) at (2,4) [small, label=above:$r$] {};
        \node (cp) at (3.11,1.92) [smaller, label=right:$c_P$] {};
        \node (cq) at (2.5,1.77) [smaller, label=left:$c_Q$] {};
        \node (cr) at (2.8,1.275) [smaller, label=below:$c_R$] {};

        \draw[decoration={markings, mark=at position 86.84-15 pt with \node[zero] (pq-1) {};, mark=at position 86.84-10 pt with \node[zero] (pq0) {};, mark=at position 86.84-5 pt with \node[zero] (pq1) {};, mark=at position 86.84 pt with \node[tiny] (pq2) {};, mark=at position 185.0166-98.1766 pt with \node[zero] (qp2) {};, mark=at position 86.84+5 pt with \node[zero] (qp1) {};, mark=at position 86.84+10 pt with \node[zero] (qp0) {};, mark=at position 86.84+15 pt with \node[zero] (qp-1) {};}, postaction={decorate}]
(p) .. controls (3,1.7)  .. node[pos=.5,below=5mm] {$R$} (q);

        \draw[decoration={markings, mark=at position 86.84-15 pt with \node[zero] (pr-1) {};, mark=at position 86.84-10 pt with \node[zero] (pr0) {};, mark=at position 86.84-5 pt with \node[zero] (pr1) {};, mark=at position 86.84 pt with \node[tiny] (pr2) {};, mark=at position 152.72462-65.8846 pt with \node[zero] (rp2) {};, mark=at position 86.84+5 pt with \node[zero] (rp1) {};, mark=at position 86.84+10 pt with \node[zero] (rp0) {}; , mark=at position 86.84+15 pt with \node[zero] (rp-1) {};}, postaction={decorate}]
(p) .. controls (3,1.7)  .. node[pos=.5,left=8mm] {$Q$} (r);

        \draw[decoration={markings, mark=at position 98.1766-15 pt with \node[zero] (qr-1) {};, mark=at position 98.1766-10 pt with \node[zero] (qr0) {};, mark=at position 98.1766-5 pt with \node[zero] (qr1) {};, mark=at position 98.1766 pt with \node[tiny] (qr2) {};,mark=at position 164.06123-65.8846 pt with \node[zero] (rq2) {};, mark=at position 98.1766+5 pt with \node[zero] (rq1) {};, mark=at position 98.1766+10 pt with \node[zero] (rq0) {};, mark=at position 98.1766+15 pt with \node[zero] (rq-1) {};}, postaction={decorate}]
(q) .. controls (3,1.7)  .. node[pos=.55,right=8mm] {$P$} (r);

        \draw[densely dotted, bend angle=20, bend right] (pq-1) to  (pr-1);
        \draw[densely dotted, bend angle=20, bend left] (qp-1) to  (qr-1);
        \draw[densely dotted, bend angle=20, bend right] (rp-1) to  (rq-1);

        \draw[densely dotted, bend angle=20, bend right] (pq0) to  (pr0);
        \draw[densely dotted, bend angle=20, bend left] (qp0) to  (qr0);
        \draw[densely dotted, bend angle=20, bend right] (rp0) to  (rq0);

        \draw[densely dotted, bend angle=20, bend right] (pq1) to  (pr1);
        \draw[densely dotted, bend angle=20, bend left] (qp1) to  (qr1);
        \draw[densely dotted, bend angle=20, bend right] (rp1) to  (rq1);

        \draw[densely dotted, bend angle=20, bend right] (pq2) to  (pr2);
        \draw[densely dotted, bend angle=20, bend left] (qp2) to  (qr2);
        \draw[densely dotted, bend angle=20, bend right] (rp2) to  (rq2);

      \end{tikzpicture}}}
  \caption{ A geodesic triangle in a hyperbolic metric space.  Note
    how the three sides ``bow in'' to a common centre.  Dotted lines
    represent paths of length at most $\delta$ between corresponding
    points. }
  \label{fig-triangle}
\end{figure}

We now fix a group $G$ and a symmetric generating set $\Sigma$; we assume that $G$ (that is, $\Gamma = \Gamma(G, \Sigma)$) is $\delta$--hyperbolic.
We choose $\delta$ large enough to ensure that all geodesic triangles in $\Gamma$ are $\delta$-thin.

\begin{remark*}
From a computational viewpoint, hyperbolic groups have many nice properties.  For example, their word problems can be solved in linear time~\cite[Theorem 2.18]{ABCFLMSS91} as can their conjugacy problems~\cite{EpsteinH06}.  (Here we gloss over the details of the required model of computation.)
Other positive algorithmic results can be found in~\cite{BuckleyHolt13, CiobanuElder19, DaGui10, DaGui11, Loh2019}.
\end{remark*}

The following results come from the fact that hyperbolic groups have automatic structures with respect to any shortlex ordering.

\begin{lemma}[\mbox{\cite[Theorem~2.3.10]{ECHLPT}}]
\label{lem-shortlex-reduction}
There is a polynomial-time (in fact, quadratic) algorithm that, given a word $w \in \Sigma^*$, produces $\mathsf{slex}(w)$.  \qed
\end{lemma}

\begin{lemma}[\mbox{\cite[Proposition~2.5.11 and Theorem~3.4.5]{ECHLPT}}]
\label{lem-shortlex-regular}
The languages in $\Sigma^*$, of geodesic words and of shortlex reduced words, are regular.  \qed
\end{lemma}

\begin{remark}
\label{rem-why-both}
We will in fact need both geodesic and shortlex reduced words in our proof of Theorem~\ref{thm-SLP-for-shortlex}.
This is because the inverse of a geodesic word is again geodesic; this need not be the case for shortlex reduced words.
On the other hand, shortlex reduced words provide unique representatives of group elements; this is almost never the case for geodesic words.
\end{remark}

\begin{figure}
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \tikzstyle{small} = [circle,draw=black,fill=black,inner sep=.15mm]
        \tikzstyle{zero} = [circle,inner sep=0mm]

        \node[small] (1) {} ;
        \node[small,  right = 3cm of 1] (a) {} ;
        \node[small,  above = 0.68cm of a] (b) {} ;
        \node[small,  right = 6cm of 1] (2) {};
        \node[small,  above = 1.5cm of 1] (3) {};
        \node[small,  right = 6cm of 3] (4) {};

        \node[zero,  below = .6mm of 1] (1') {};
        \node[zero,  below = .6mm of 2] (2') {};
        \node[zero,  above = .6mm of 3] (3') {};
        \node[zero,  above = .6mm of 4] (4') {};

        \draw [->] (3) to [out=-27, in=-180] node[pos = 0.5, below = -0.7mm] {$v'$} (b);
        \draw [->] (b) to [out=0, in=-153] node[pos = 0.5, below = -0.7mm]  {$v''$} (4);
        \draw [->] (3') to [out=-27, in=-153] node[pos = 0.33, above = -0.7mm]{$v$} (4');

        \draw [->] (3) edge node[left=-.7mm]{$a$} (1);
        \draw [<-] (2) edge node[right=-.7mm]{$b$} (4);
        \draw [->] (1') edge node[pos = 0.33, below=-.7mm]{$u$} (2');
        \draw [->] (1) edge node[above=-.7mm]{$u'$} (a);
        \draw [->] (a) edge node[above=-.7mm]{$u''$} (2);
        \draw [<-] (a) edge node[left=-.7mm]{$c$} (b);

  \end{tikzpicture}}}
  \caption{Splitting a geodesic quadrilateral according to Lemma~\ref{lem-quad}.}
  \label{fig-quad}
\end{figure}

We will need the following standard lemmas on geodesic quadrilaterals.

\begin{lemma}
\label{lem-quad}
Let $a, b, u, v \in \Sigma^*$ be geodesic words such that $v b =_G a u$.
Suppose that $u$ has a factorization $u = u' u''$ with $|u'| \geq |a| + 2 \delta$ and $|u''| \geq |b| + 2 \delta$.
Then there exists a factorization $v = v' v''$ and a geodesic word $c$ so that
\begin{itemize}
\item
$|c| \leq 2\delta$,
\item
$v' c =_G a u'$, and
\item
$v'' b =_G c u''$.
\end{itemize}
\end{lemma}

\begin{proof}
We consider the quadrilateral with sides $P_v$, $P_a$, $g_a \cdot P_u$, and $g_{v} \cdot P_b$.
Here $g_w$ is the group element represented by the word $w$.
We are given a factorization $u = u' u''$.  Set $g = g_a g_{u'}$ and note that $g$ lies in $g_a \cdot P_u$.
See Figure~\ref{fig-quad}.
Since geodesic quadrilaterals are $2\delta$--slim there is a group element $h$ with $d_\Gamma(g, h) \leq 2\delta$ lying in the union of the three other sides.

We now consider cases.
Suppose that $h$ lies in $P_a - \{1_G\}$.
Then the triangle inequality implies $|u'| < |a| + 2\delta$.
Similarly, if $h$ lies in $g_{v} P_b - \{g_{v}\}$, then $|u''| < |b| + 2\delta$.
Both of these are contrary to hypothesis.
We deduce that $h$ lies in $P_v$, proving the lemma.
\end{proof}

\begin{lemma}
\label{lem-quad-two}
Let $a, b, u, v \in \Sigma^*$ be geodesic words such that $v b =_G a u$.
Suppose that $u$ has a factorization $u = u' u'' u'''$ with $|u'| \geq |a| + 2\delta$, $|u''| \geq 4\delta$, and $|u'''| \geq |b|+2\delta$.
Then there exists a factorization $v = v' v'' v'''$ and geodesic words $c, d$ so that
\begin{itemize}
\item
$|c|, |d| \leq 2\delta$,
\item
$v' c =_G a u'$,
\item
$v'' d =_G c u''$, and
\item
$v''' b =_G d u'''$.
\end{itemize}
\end{lemma}

\begin{proof}
We prove this via two applications of Lemma~\ref{lem-quad}.
The first application gives us $c$.
In the second application we restrict our attention to the quadrilateral with sides labelled $c$, $b$, $u'' \cdot u'''$, and the fourth side labelled by the resulting suffix of $v$.
This gives $d$.
\end{proof}

Suppose that $S$ is a path in $\Gamma$ of length $n$, and $i$ is an integer.
We adopt the convention that the expression $S(i)$ implies that $i$ lies in $[0, n]$.
Recall that $\bar{S}$ denotes $S$ with its parametrization reversed.

\begin{lemma}
\label{lem-thin-triangle}
Let $T$ be a $\delta$--thin geodesic triangle with vertices at $p$, $q$, and $r$ and with sides $P$, $Q$, and $R$.
Suppose that $P(0) = q = \bar{R}(0)$, $Q(0) = r = \bar{P}(0)$, and $R(0) = p = \bar{Q}(0)$.
Let $j$ be any integer so that $d_\Gamma(R(j), \bar{Q}(j)) > \delta$.
Then there are integers $i_R < i_Q$ so that $d_\Gamma(R(j), P(i_R)) \leq \delta$ and $d_\Gamma(\bar{Q}(j), P(i_Q)) \leq \delta$.
\end{lemma}

In the statement and the proof we follow the notation of Figure~\ref{fig-triangle}.

\begin{proof}[Proof of Lemma~\ref{lem-thin-triangle}]
Since $d_\Gamma( R(j), \bar{Q}(j) ) > \delta$, the group elements $R(j)$ and $\bar{Q}(j)$ do not correspond to each other.
Thus $R(j)$ is strictly after the meeting point $c_R$ along $R$.
Similarly $\bar{Q}(j)$ is strictly after the meeting point $c_Q$ along $\bar{Q}$.
Since $T$ is $\delta$--thin,
there are integers $i_R$ and $i_Q$ so that
\begin{itemize}
\item
$R(j)$ corresponds to $P(i_R)$ and so $d_\Gamma(R(j), P(i_R)) \leq \delta$ and
\item
$\bar{Q}(j)$ corresponds to $P(i_Q)$ and so $d_\Gamma(\bar{Q}(j), P(i_Q)) \leq \delta$.
\end{itemize}
We deduce that $P(i_R)$ is strictly before, and $P(i_Q)$ is strictly after, $c_P$ along $P$.
Thus $i_R < i_Q$ and we are done.
\end{proof}

\section{Compressed words and the compressed word problem}
\label{sec-SLP}

\subsection{Straight-line programs}
\label{sec-SLP-def}

Straight-line programs offer succinct representations of long words that contain many repeated substrings.
We here review the basics, referring to~\cite{Loh14} for a more in-depth introduction.

\begin{definition}
Fix $\Sigma$, a finite alphabet.  A \emph{straight-line program} over $\Sigma$ is a triple ${\mathcal{G}} = (V, S, \rho)$ where
\begin{itemize}
\item
$V$ is a finite set of \emph{variables}, disjoint from $\Sigma$,
\item
$S \in V$ is the \emph{start variable}, and
\item
$\rho$ is an \emph{acyclic production rule}: that is, for $A \in V$ the \emph{right-hand side} $\rho(A)$ is a word in $(V \cup \Sigma)^*$ and the resulting relation
\[
\{ (B,A) \in V \times V \st \mbox{$B$ appears in $\rho(A)$} \}
\]
is acyclic.
\end{itemize}
\end{definition}

\begin{example}
\label{exam-double}
Let $\Sigma = \{a, b\}$ and fix $n \geq 0$.
We define ${\mathcal{G}}_n = (\{A_0, \ldots, A_n\}, A_n, \rho)$.
Here $\rho(A_0) = ab$ and where $\rho(A_{i+1}) = A_i A_i$ for $0 \leq i \leq n - 1$.
\end{example}

\begin{definition}
Given ${\mathcal{G}}$, we define a \emph{evaluation} function $\mathsf{eval} = \mathsf{eval}_{\mathcal{G}} \colon (V \cup \Sigma)^* \to \Sigma^*$ as follows.
\begin{itemize}
\item
$\mathsf{eval}(a) = a$ for $a \in \Sigma$,
\item
$\mathsf{eval}(uv) = \mathsf{eval}(u)\mathsf{eval}(v)$ for $uv \in (V \cup \Sigma)^*$, and
\item
$\mathsf{eval}(A) = \mathsf{eval}(\rho(A))$ for $A \in V$.
\end{itemize}
One proves by a delicate induction that $\mathsf{eval}$ is well defined.
We finally take $\mathsf{eval}({\mathcal{G}}) = \mathsf{eval}(S)$.
We call $\mathsf{eval}({\mathcal{G}})$ the \emph{output} of the program ${\mathcal{G}}$.
\end{definition}

In other words, ${\mathcal{G}}$ is a context-free grammar that generates exactly one word $\mathsf{eval}({\mathcal{G}})$ of $\Sigma^*$.

So, continuing Example~\ref{exam-double} above we have $\mathsf{eval}(A_0) = ab$ and more generally $\mathsf{eval}(A_i) = (ab)^{2^i}$.
Thus $\mathsf{eval}({\mathcal{G}}_n) = \mathsf{eval}(A_n) = (ab)^{2^n}$.
So the output has length $2^{n+1}$.

We say a straight-line program ${\mathcal{G}} = (V, S, \rho)$ over $\Sigma$ is \emph{trivial} if $S$ is the only variable and $\rho(S) = \varepsilon = \mathsf{eval}({\mathcal{G}})$.

We say that a straight-line program is in \emph{Chomsky normal form} if it is either a trivial program or all right-hand sides are of the form $a \in \Sigma$ or $BC$ with $B, C \in V$.
There is a linear-time algorithm that transforms a given straight-line program ${\mathcal{G}}$ into a program ${\mathcal{G}}'$ in Chomsky normal form with the same output.
See~\cite[Proposition~3.8]{Loh14}.

\begin{definition}
We define the \emph{size} $|{\mathcal{G}}|$ of ${\mathcal{G}} = (V, S, \rho)$ to be the sum of the bit-lengths of the right-hand sides of $\rho$.
\end{definition}

Again considering Example~\ref{exam-double}, we see that the size of ${\mathcal{G}}_n$ is $O(n \log(n))$.
(Note that we take into account the cost of writing out the indices of the variables $A_i$.)
Thus we see that straight-line programs can achieve (essentially) exponential compression.
The following result proves that straight-line programs can do no better;
the proof follows the proof of~\cite[Lemma~1]{CLLLPPSS05}.

\begin{lemma}
\label{lem-SLP-upper-bound}
For every straight-line program ${\mathcal{G}}$ we have $|\mathsf{eval}({\mathcal{G}})| \leq  3^{|{\mathcal{G}}|/3}$. \qed
\end{lemma}

As a convenient short-hand, we will refer to straight-line programs over $\Sigma$ as \emph{compressed words}.

\subsection{Algorithms for compressed words}
\label{subsec-algo-compressed}

We will assume that all integers given as input to algorithms are given in binary.
We will need to know that the following algorithmic tasks can be solved in polynomial time; see~\cite[Proposition~3.9]{Loh14}.

Given a straight-line program ${\mathcal{G}}$ and natural numbers $i \leq j$:
\begin{itemize}
\item find the length $|\mathsf{eval}({\mathcal{G}})|$;
\item find the letter $\mathsf{eval}({\mathcal{G}})[i]$;
\item find a straight-line program ${\mathcal{G}}'$ with $\mathsf{eval}({\mathcal{G}}') = \mathsf{eval}({\mathcal{G}})[i:j]$.
\end{itemize}

The following proposition is also well-known.

\begin{proposition}[\mbox{\cite[Lemma~2]{CLLLPPSS05}}]
\label{prop-power}
There is a polynomial-time algorithm that, given a straight-line program ${\mathcal{G}}$ and a natural number $n > 0$, computes a straight-line program ${\mathcal{G}}_n$ with $\mathsf{eval}({\mathcal{G}}_n) = \mathsf{eval}({\mathcal{G}})^n$.  In fact, the time required is linear in $|{\mathcal{G}}| + \log n$. \qed
\end{proposition}

The following results are less trivial.
A proof of this proposition can be found in~\cite[Theorem 3.11]{Loh14}.

\begin{proposition}
\label{prop-fsa}
There is a polynomial-time algorithm that, given
\begin{itemize}
\item
a finite alphabet $\Sigma$,
\item
a finite state automaton $M$ over $\Sigma$, and
\item
a straight-line program ${\mathcal{G}}$ over $\Sigma$,
\end{itemize}
decides if $\mathsf{eval}({\mathcal{G}})$ lies in the language $L(M)$. \qed
\end{proposition}

We also need the following variant of Proposition~\ref{prop-fsa}.

\begin{proposition}
\label{prop-fsa-2}
There is a polynomial-time algorithm that, given
\begin{itemize}
\item
a finite alphabet $\Sigma$,
\item
a finite state automaton $M$ over $\Sigma$, and
\item
a straight-line program ${\mathcal{G}}$ over $\Sigma$,
\end{itemize}
decides if $\{ \mathsf{eval}({\mathcal{G}})^n \st n \in \mathbb{N} \}$ is a subset of $L(M)$.
\end{proposition}

\begin{proof}
Let $M = (Q, \Sigma, q_0, \delta, F)$ be the automaton.
Suppose that $w = \mathsf{eval}({\mathcal{G}})$.
All non-negative powers of $w$ belong to $L(M)$ if and only if $\delta(q_0, w^n)$ lies in $F$, for all $n \geq 0$.

Since $Q$ is finite, if the latter holds then there are natural numbers $k$ and $l$, with $0 \leq k < l \leq |Q|$ such that
\[
\delta(q_0, w^k) = \delta(q_0, w^l)
\]
It follows that $w^n \in L(M)$ for all $n \geq 0$ if and only if $w^n \in L(M)$ for all $0 \leq n \leq |Q|$.
By Proposition~\ref{prop-power}, we can compute, in polynomial time and for all $0 \leq n \leq |Q|$, a straight-line program ${\mathcal{G}}_n$ with output $\mathsf{eval}({\mathcal{G}}_n) = w^n$.
Finally we use Proposition~\ref{prop-fsa} to test, in polynomial time, if $\mathsf{eval}({\mathcal{G}}_n) \in L(M)$ for these programs.
\end{proof}

The following theorem of Plandowski~\cite{Pla94} is central to our work here.

\begin{theorem}[\mbox{\cite{Pla94}}]
\label{thm-plandowski}
There is a polynomial-time algorithm that, given straight-line programs ${\mathcal{G}}$ and ${\mathcal{H}}$, decides if $\mathsf{eval}({\mathcal{G}}) = \mathsf{eval}({\mathcal{H}})$. \qed
\end{theorem}

The following result generalizes Theorem~\ref{thm-plandowski} to the so-called \emph{fully compressed pattern matching problem}.

\begin{theorem}[\mbox{\cite{KarpinskiEtAl95}}]
\label{thm-pattern-matching}
There is a polynomial-time algorithm that, given straight-line programs ${\mathcal{G}}$ and ${\mathcal{H}}$, decides if $\mathsf{eval}({\mathcal{G}})$ is a factor of $\mathsf{eval}({\mathcal{H}})$.
Furthermore, if it is a factor, the algorithm returns (in binary) the smallest $m \in \mathbb{N}$ so that $\mathsf{eval}({\mathcal{G}})$ is a prefix of $\mathsf{eval}({\mathcal{H}})[n:]$. \qed
\end{theorem}

We obtain the following corollary of Theorem~\ref{thm-pattern-matching} and Lemma~\ref{lem-rotation}.

\begin{corollary}
\label{coro-cyclic-conj}
There is a polynomial-time algorithm that, given straight-line programs ${\mathcal{G}}$ and ${\mathcal{H}}$, decides if $\mathsf{eval}({\mathcal{G}})$ is a rotation of $\mathsf{eval}({\mathcal{H}})$.
Furthermore, if it is, then the algorithm returns straight-line programs ${\mathcal{H}}'$ and ${\mathcal{H}}''$ such that
\[
\pushQED{\qed}
\mathsf{eval}({\mathcal{H}}) = \mathsf{eval}({\mathcal{H}}') \mathsf{eval}({\mathcal{H}}'')
    \qquad \mbox{and} \qquad
\mathsf{eval}({\mathcal{G}}) = \mathsf{eval}({\mathcal{H}}'') \mathsf{eval}({\mathcal{H}}')  \qedhere
\popQED
\]
\end{corollary}

\subsection{The compressed word problem}

Suppose that $G$ is a group and $\Sigma$ is a finite symmetric generating set.  The \emph{compressed word problem} for $G$, over $\Sigma$, is the following decision problem.

\begin{description}
\item [Input] A straight-line program ${\mathcal{G}}$ over $\Sigma$.
\item [Question] Does $\mathsf{eval}({\mathcal{G}})$ represent the identity of $G$?
\end{description}

Clearly, the compressed word problem for a group $G$ is decidable if and only if the word problem for $G$ is decidable.
Under some standard computational hardness assumptions, there are in fact groups $G$ where the compressed word problem is strictly harder than the word problem itself.

Observe that the computational complexity of the compressed word problem for $G$ does not depend on the chosen generating set $\Sigma$.
That is, if $\Sigma'$ is another such, then the compressed word problem for $G$ over $\Sigma$ is logspace reducible to the compressed word problem for $G$ over $\Sigma'$~\cite[Lemma~4.2]{Loh14}.
Thus, when proving that the compressed word problem is polynomial time, we are allowed to use whatever generating set is most convenient for our purposes.

\begin{remark}
\label{rem-inverse}
As a simple but useful tool, note that if ${\mathcal{G}}$ is a straight-line program over $\Sigma$ with output $w$ then there is a straight-line program $\bar{{\mathcal{G}}}$ with output $w^{-1}$.
\end{remark}

\subsection{Cut programs}
\label{sec-cut}

A useful generalization of straight-line programs are the \emph{composition systems} of~\cite{Hag00}.
These are also called \emph{cut straight-line programs} in \cite{Loh14}.  We shall simply call them \emph{cut programs}.
They are used, for example, in the polynomial-time algorithm for the compressed word problem of a free group~\cite{Loh06siam}.

A \emph{cut program} over $\Sigma$ is a tuple ${\mathcal{G}} = (V, S, \rho)$, with $V$ and $S$ as in Section~\ref{sec-SLP-def}, and where we also allow, as right-hand sides for $\rho$, expressions of the form $B[i:j]$, with $B \in V$ and with $i \leq j$.
We again require $\rho$ to be acyclic.
When $\rho(A) = B[i:j]$ we define
\[
\mathsf{eval}(A) = \mathsf{eval}(B)[i:j]
\]
with the cut operator $[i:j]$ as defined in Section~\ref{sec-notation}.
The \emph{size} of a cut program ${\mathcal{G}}$ is the sum of the bit-lengths of the right-hand sides; as usual all natural numbers are written in binary.

We can now state a straight-forward but important result of Hagenah~\cite{Hag00}; see also~\cite[Theorem~3.14]{Loh14}.

\begin{theorem}[\mbox{\cite{Hag00}}]
\label{thm-hagenah}
There is a polynomial-time algorithm that, given a cut program ${\mathcal{G}}$, finds a straight-line program ${\mathcal{G}}'$ such that
$\mathsf{eval}({\mathcal{G}}) = \mathsf{eval}({\mathcal{G}}')$.
\end{theorem}

Theorems~\ref{thm-plandowski} and~\ref{thm-hagenah} imply that there is a polynomial-time algorithm that, given two cut programs, decides if they have the same output.

\begin{remark}
In fact, in what follows, we will only ever need the prefix and suffix cut operators $[:j]$ and $[i:]$.
This is because, when using a word to represent a group element, cancellation appears where two factors meet.

We also note that iterating the cut operator can be done using arithmetic alone.  That is, the cut variables
\[
B[i:j][k:\ell] \quad \mbox{and} \quad B[i+k:i+\ell]
\]
have the same evaluation.
This ``cut elimination'' is, in some sense, the heart of the proof of Theorem~\ref{thm-hagenah}.
\end{remark}

\section{The compressed word problem for hyperbolic groups}

Suppose that $G$ is a group and $\Sigma$ is a finite symmetric generating set.
Suppose that $G$ is $\delta$--hyperbolic; here we take $\delta$ large enough so that all geodesic triangles are $\delta$--thin.
Moreover we choose $\delta > 0$ to be an integer.
In what follows, we take $\zeta = 2 \delta$.  Recall that ${\sf{Ball}}(r)$ is the ball of radius $r$ about $1_G$ in the Cayley graph $\Gamma = \Gamma(G, \Sigma)$.

\subsection{Tethered programs}
\label{subsec-tethered}

We introduce a new type of program using the \emph{tether} operator.

A \emph{tethered program} over $\Sigma$ is a tuple ${\mathcal{G}} = (V, S, \rho)$, with $V$ and $S$ as in Section~\ref{sec-SLP-def}, and where we also allow, as right-hand sides for $\rho$, expressions of the form $B\teth{a, b}$, with $B \in V$ and with $a, b \in {\sf{Ball}}(\zeta)$.
We again require $\rho$ to be acyclic.
If $\rho(A) = B\teth{a, b}$ then we define
\[
\mathsf{eval}(A) = \mathsf{slex}(a \cdot \mathsf{eval}(B) \cdot b^{-1})
\]
We call the suffix $\teth{a, b}$ a \emph{tether} operator.
The \emph{size} of a tethered program ${\mathcal{G}}$ is the sum of the bit-lengths of the right-hand sides; group elements in ${\sf{Ball}}(\zeta)$ are represented by their shortlex representatives.

Finally, in a \emph{tether-cut} program ${\mathcal{G}}$ over $\Sigma$ we allow right-hand sides which are words from $(V \cup \Sigma)^*$, a cut variable, or a tethered variable.  It sometimes convenient to allow more complicated right-hand sides such as
\[
B[:i] \teth{a, b} \cdot C[j:] \teth{c, d}
\]
We define the size of ${\mathcal{G}}$ as above.  In what follows we will assume that all programs arising are over a fixed alphabet $\Sigma$.

\begin{remark}
\label{rem-double-tether}
In what follows we mostly need the prefix and suffix tether operators $\teth{a, 1}$ and $\teth{1, b}$.
For, suppose that $\Gamma(G, \Sigma)$ is hyperbolic and that $u$ and $v$ are geodesic words.
Let $w =_G uv$ be a geodesic word representing their product.
Then we can describe $w$ (up to bounded Hausdorff distance) by taking a prefix of $u$, tethering the result at the end, concatenating with a short word, and then tethering (at the front) a suffix of $v$.
See Figure~\ref{fig-cutting-off-peak} below.

We also note that iterating tether operators can be done ``locally''.
That is, for any $a, a', b, b' \in {\sf{Ball}}(\zeta)$ there are elements $a'', b'' \in {\sf{Ball}}(\zeta)$, elements $x, y \in {\sf{Ball}}(2\zeta)$, and natural numbers $i, j$ so that the expressions
\[
B \teth{a, b} \teth{a',b'}
\quad \mbox{and} \quad
x \cdot B[i:j] \teth{a'', b''} \cdot y
\]
have the same evaluation: that is, they represent the same shortlex reduced word.
See Figure~\ref{fig-iterated-tether}.
Again, this ``tether-elimination'' is, in some sense, the heart of our proof of Lemma~\ref{lem-TSLP-SLP}.
\end{remark}

\begin{figure}
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \tikzstyle{small} = [circle, draw = black, fill = black, inner sep = .15mm]
        \tikzstyle{zero} = [circle, inner sep = 0mm]

        \node[small] (1) {} ;
        \node[small, right = 9cm of 1] (2) {};

        \node[zero,  above = 1.5cm of 1] (1u) {};
        \node[zero,  above = 1.5cm of 2] (2u) {};
        \node[zero,  below = 1.5cm of 1] (1d) {};
        \node[zero,  below = 1.5cm of 2] (2d) {};

        \node[small, right = 1.5cm of 1u] (3) {};
        \node[small, left  = 1.5cm of 2u] (4) {};
        \node[small, right = 1.5cm of 1d] (5) {};
        \node[small, left  = 1.5cm of 2d] (6) {};
        \node[zero, right  = 1.15cm of 3] (3r) {};
        \node[small, below  = 0.5cm of 3r] (3') {};
        \node[zero, left  = 1.15cm of 4] (4l) {};
        \node[small, below  = 0.5cm of 4l] (4') {};
        \node[zero, right  = 2.05cm of 5] (5r) {};
        \node[small, above  = 0.75cm of 5r] (5') {};
        \node[zero, left  = 2.05cm of 6] (6l) {};
        \node[small, above  = 0.75cm of 6l] (6') {};

        \draw [->] (3) to [out=-30, in=160] node[pos = 0.5, above right = -0.7mm]{$x$} (3');
	\draw [->] (3') to [out=-20, in=-160] node[pos = 0.5, above = -0.4mm]{$w''$} (4');
	\draw [->] (4') to [out=20, in=-150]
                                             node[pos = 0.5, above left = -0.7mm]{$y$}  (4);
        \draw [->] (1) edge node[below = -0.7mm]{} (2);
        \draw [->] (5) to [out=30, in=-170] node[pos = 0.5, below right = -0.7mm]{$u'$} (5');
	\draw [->] (5') to [out=10, in=170] node[pos = 0.5, below = -0.4mm]{$u''$} (6');
	\draw [->] (6') to [out=-10, in=150]
                                             node[pos = 0.6, below left = -0.7mm]{$u'''$}  (6);
        \draw [->] (1) to [out=-30, in=120] node[below left = -0.7mm]{$a$} (5);
        \draw [->] (2) to [out=-150, in=60] node[below right =-0.7mm]{$b$} (6);

        \draw [->] (3) to [out=-120, in=30] node[above left = -0.7mm]{$a'$} (1);
        \draw [->] (4) to [out=-60, in=150] node[above right =-0.7mm]{$b'$} (2);

        \draw [->] (3') to [out=-50, in =105] node[pos = 0.25, below left = -1.0mm]{$a''$} (5');
        \draw [->] (4') to [out=-130, in=75] node[pos = 0.25, below right = -1.0mm]{$b''$} (6');

  \end{tikzpicture}}}
  \caption{The evaluation of $B\teth{a, b}\teth{a', b'}$ agrees with the evaluation of $x \cdot B[i:j]\teth{a'', b''} \cdot y$.  Here we are assuming that $\mathsf{eval}(B) = u = u'u''u'''$ and that $\mathsf{eval}(B[i:j]\teth{a'', b''}) = w''$.}
  \label{fig-iterated-tether}
\end{figure}

We say that a program is in \emph{Chomsky normal form} if it is either a trivial program or
\begin{itemize}
\item
all right hand sides of productions that lie in $(V \cup \Sigma)^*$ are of the form $a \in \Sigma$ or $BC$ with $B, C \in V$ and
\item
all other right-hand sides involve exactly one variable and exactly one operator (either tether or cut).
\end{itemize}
Similar to the case of straight-line programs, there is a linear-time algorithm that transforms a given program ${\mathcal{G}}$ (with $\mathsf{eval}({\mathcal{G}}) \neq \varepsilon$) into a program ${\mathcal{G}}'$ in Chomsky normal form with the same output.

We say that a program ${\mathcal{G}}$ is \emph{geodesic} (or \emph{shortlex}) if for every variable $A$, the word $\mathsf{eval}(A)$ is geodesic (shortlex reduced).

\begin{lemma}
\label{lem-CNF}
There is a polynomial-time algorithm that, given a geodesic tether-cut program ${\mathcal{G}}$, returns a geodesic tether-cut program ${\mathcal{G}}'$ with the same evaluation which is in Chomsky normal form.
\end{lemma}

\begin{proof}
We essentially use the usual algorithm; see, for example~\cite[Proposition~3.8]{Loh14}.
However, some care must be taken with tethered variables.
If $\rho(A) = B \teth{a, b}$ and $\rho(B) = \varepsilon$ then we set $\rho(A) = \mathsf{slex}(a b^{-1})$ and repeat the process.
\end{proof}

Note that the concatenation of geodesic words may not itself be geodesic; however the concatenation does provide two sides of a geodesic triangle.
When the group $G$ is hyperbolic, this gives us the beginnings of a reduction procedure.

In this section we will prove Lemma~\ref{lem-TCSLP-SLP}; we will give a sequence of results that allows us to transform a geodesic tether-cut program into a straight-line program, whose evaluation is the shortlex representative of the original.
The first step, in Lemma~\ref{lem-TSLP-SLP}, gives such a transformation for tethered programs.
The second step, finishing the proof of Lemma~\ref{lem-TCSLP-SLP}, is to transform a geodesic tether-cut program into an geodesic tethered program with the same output.
This second step is inspired by Hagenah's result (Theorem~\ref{thm-hagenah}) transforming a cut program into an equivalent straight line program.

\subsection{Transforming tethered programs}

Suppose that ${\mathcal{G}} = (V, S, \rho)$ is a program, as above.

We recursively define the \emph{height} of elements of $\Sigma \cup V$.
If $a \in \Sigma$ then we take $\mathsf{height}(a) = 0$.
For $A \in V$ we define
\[
\mathsf{height}(A) = \max \{ \mathsf{height}(B) + 1 \st \mbox{$B \in \Sigma \cup V$ occurs in $\rho(A)$} \}
\]
Finally we set $\mathsf{height}({\mathcal{G}}) = \mathsf{height}(S)$.

Suppose that ${\mathcal{G}}$ is a tethered program in Chomsky normal form.
If $A \in V$ is a variable we define its \emph{tether-height}, denoted $\mathsf{height}_t(A)$, recursively as follows.
\begin{itemize}
\item If $\rho(A) = a$, then $\mathsf{height}_t(A) = 0$,
\item if $\rho(A) = BC$, then $\mathsf{height}_t(A)= \max \{ \mathsf{height}_t(B), \mathsf{height}_t(C)\}$, and
\item if $\rho(A) = B \teth{s, t}$ then $\mathsf{height}_t(A) = \mathsf{height}_t(B) + 1$.
\end{itemize}
For a variable $A$ we define its \emph{tether-depth} to be
\[
\mathsf{depth}_t(A) = \mathsf{height}_t(S) - \mathsf{height}_t(A) + 1
\]

\begin{lemma}
\label{lem-TSLP-SLP}
There is a polynomial-time algorithm that, given a geodesic tethered program ${\mathcal{G}}$, finds a straight-line program ${\mathcal{G}}'$ so that $\mathsf{eval}({\mathcal{G}}') = \mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$.
\end{lemma}

\begin{proof}
Set ${\mathcal{G}} = (V, S, \rho)$.
Applying Lemma~\ref{lem-CNF} we may assume that ${\mathcal{G}}$ is in Chomsky normal form.
Introducing a new start variable, if needed, we may assume that $\rho(S)$ has the form $A \teth{1, 1}$ for a variable $A$.
We do this to force the evaluation of ${\mathcal{G}}$ to be shortlex reduced, not just geodesic.
By removing unused variables, we can assume that $S$ has maximal height and maximal tether-height among all variables.
This implies that, for all $A \in V$, the tether-depth of $A$ is greater than zero.

We carry out the proof in a bottom-up fashion; that is, we consider the variables of ${\mathcal{G}}$ in order of increasing height.
Here is an outline of the proof; we give the details below.
Set $w = \mathsf{eval}(A)$.
If $|w| \leq 16 \zeta \mathsf{depth}_t(A) + 2\zeta$ then we compute and record $w$, as a word.
If $w$ is longer than that, then we instead compute words $\ell_A$ and $r_A$ such that
\[
w = \ell_A \cdot w' \cdot r_A
\]
for some word $w'$ of length at least $2 \zeta$.
The details of the computation depend on the production $\rho(A)$.
We require that the word $\ell_A$ satisfies the following length constraint
\begin{equation}
\label{equ-length}
8 \zeta \mathsf{depth}_t(A) \leq |\ell_A| \le 8 \zeta \mathsf{depth}_t(A) + 2\zeta \mathsf{height}(A)
\end{equation}
and similarly for $r_A$.

When $w$ is long, we also add to the program ${\mathcal{G}}'$ the \emph{decorated} variables $A'_{a,b}$ for all $a, b \in {\sf{Ball}}(\zeta)$.
We arrange the following:
\[
\mathsf{eval}(A'_{a,b}) = \mathsf{slex}(a w' b^{-1})
\]
These new variables $A'_{a,b}$, and also a new start variable $S'$, are the \emph{only} variables appearing in ${\mathcal{G}}'$.
All of the words that we compute and record along the way, such as the short words $w$ and the prefixes and suffixes $\ell_A$ and $r_A$, are not separately stored as part of ${\mathcal{G}}'$.

That completes our outline of the proof.
We now consider the possibilities for the right-hand side $\rho(A)$.

\begin{case}
Suppose $\rho(A) \in \Sigma$.
Thus $w = \mathsf{eval}(A)$ is geodesic and shorter than $16 \zeta \mathsf{depth}_t(A) + 2\zeta$.  We record it and continue.
\end{case}

\begin{case}
Suppose $\rho(A) = BC$ for variables $B$ and $C$.
By adding dummy variables to ${\mathcal{G}}$, with productions of the form $X\teth{1, 1}$, as needed, we may assume that
\[
\mathsf{depth}_t(A) = \mathsf{depth}_t(B) = \mathsf{depth}_t(C)
\]
Set $\eta = \mathsf{depth}_t(A)$.
Let $u = \mathsf{eval}(B)$, let $v = \mathsf{eval}(C)$, and $w = \mathsf{eval}(A) = uv$.
Recall that $u, v, w$ are geodesic by assumption.

\begin{subcase}
\label{sub-both-long}
Suppose $|u| > 16 \zeta \eta + 2\zeta$ and $|v| > 16 \zeta \eta + 2\zeta$.
Hence, in previous stages of the algorithm we computed words $\ell_B, r_B, \ell_C, r_C$ such that the following properties hold.
\begin{itemize}
\item
The prefixes and suffixes $\ell_B, r_B, \ell_C, r_C$ satisfy the length constraint of Equation~\ref{equ-length}.
\item
There are geodesic words $u', v'$ of length at least $2 \zeta$ with $u = \ell_B \cdot u' \cdot r_B$ and $v = \ell_C \cdot v' \cdot r_C$.
\end{itemize}
Also, we have already defined variables $B'_{a,c}$ and $C'_{d,b}$ for all $a, b, c, d \in {\sf{Ball}}(\zeta)$, which produce $\mathsf{slex}(a u' c^{-1})$ and $\mathsf{slex}(d v' b^{-1})$, respectively.
See Figure~\ref{fig-both-long}.

We now set $\ell_A = \ell_B$ and $r_A = r_C$.
Since the tether-depths of $A, B, C$ are all the same, but $A$ has greater height, we deduce that $\ell_A$ and $r_A$ satisfy the length constraint of Equation~\ref{equ-length}.
We also note that
\[
|u' \cdot r_B \cdot \ell_C \cdot v'| \geq 2\zeta
\]
because $|w| = |u| + |v|$ is long enough.

It remains to define the right-hand sides for the variables $A'_{a,b}$ for all $a, b \in {\sf{Ball}}(\zeta)$.
Fix $a, b \in {\sf{Ball}}(\zeta)$.
For all $c, d \in {\sf{Ball}}(\zeta)$ we compute
\[
z = \mathsf{slex}( c \cdot r_B \cdot \ell_C \cdot d^{-1} )
\]
in polynomial time using Lemma~\ref{lem-shortlex-reduction}.
We then check, using Proposition~\ref{prop-fsa} and Lemma~\ref{lem-shortlex-regular}, whether the word
\[
\mathsf{eval}(B'_{a,c}) \cdot z \cdot \mathsf{eval}(C'_{d,b})
   = \mathsf{slex}(a u' c^{-1}) \cdot \mathsf{slex}(c \cdot r_B \cdot \ell_C \cdot d^{-1}) \cdot \mathsf{slex}(d v' b^{-1})
\]
is shortlex reduced, in which case it is equal to
\[
\mathsf{slex}(a u' \cdot r_B \cdot \ell_C \cdot v' b^{-1})
\]
By Lemma~\ref{lem-quad-two}, there must be at least one such pair $c, d$.
(If there are several, we stop as soon as we find the first such.)
We then define
\[
\rho'(A'_{a,b}) = B'_{a,c} \cdot z \cdot C'_{d,b}
\]
\end{subcase}

\begin{figure}
  \tikzstyle{vertex}=[circle, fill, inner sep=.5pt, minimum size =.5mm ]
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \node[vertex] (a) {} ;
        \node[vertex,  right = 1cm of a] (b) {};
        \node[vertex,  right = 4cm of b] (c) {};
        \node[vertex,  right = 1cm of c] (d) {};
        \node[vertex,  right = 1cm of d] (e) {};
        \node[vertex,  right = 4cm of e] (f) {};
        \node[vertex,  right = 1cm of f] (g) {};

        \node[vertex,  above = 1cm of b] (b') {};
        \node[vertex,  above = 1cm of c] (c') {};
        \node[vertex,  above = 1cm of e] (e') {};
        \node[vertex,  above = 1cm of f] (f') {};

        \draw [->](b') edge node[left=-.7mm]{$a$} (b);
        \draw [<-](c) edge node[left=-.7mm]{$c$} (c');
        \draw [->](e') edge node[right=-.7mm]{$d$} (e);
        \draw [<-](f) edge node[right=-.7mm]{$b$} (f');

        \draw [->](a) edge node[below=-.7mm]{$\ell_B$} (b);
        \draw [->, dashed](b) edge node[below=-.7mm]{$u'$} (c);
        \draw [->, dashed](b') edge node[above=-.7mm]{$\mathsf{slex}(a u' c^{-1})$} (c');
        \draw [->](c') edge node[above=-.7mm]{$z$} (e');
        \draw [->](c) edge node[below=-.7mm]{$r_B$} (d);
        \draw [->](d) edge node[below=-.7mm]{$\ell_C$} (e);
        \draw [->, dashed](e) edge node[below=-.7mm]{$v'$} (f);
        \draw [->, dashed](e') edge node[above=-.7mm]{$\mathsf{slex}(d v' b^{-1})$} (f');
        \draw [->](f) edge node[below=-.7mm]{$r_C$} (g);
  \end{tikzpicture}}}
  \label{fig-both-long}
  \caption{Case~\ref{sub-both-long} from the proof of Lemma~\ref{lem-TSLP-SLP}.  Dashed lines represent words that are given by straight-line programs. }
\end{figure}

\begin{subcase}
\label{sub-one-long}
Suppose $|u| > 16 \zeta \eta + 2\zeta$ and $|v| \leq 16 \zeta \eta + 2\zeta$.
Thus, at previous stages of the algorithm we computed the geodesic word $v$ explicitly and also computed explicit words $\ell_B$ and $r_B$ such that the following properties hold.
\begin{itemize}
\item
The prefix and suffix $\ell_B, r_B$ satisfy the length constraint of Equation~\ref{equ-length}.
\item
There is a geodesic word $u'$ of length at least $2 \zeta$ with $u = \ell_B \cdot u' \cdot r_B$.
\end{itemize}
Also, we already defined variables $B'_{a,b}$ for all $a, b \in {\sf{Ball}}(\zeta)$
such that $B'_{a,b}$ produces $\mathsf{slex}(a u' b^{-1})$.

If $|v| \leq 2\zeta$, then we set $\ell_A = \ell_B$ and $r_A = r_B v$.
In this case, we also define $\rho'(A'_{a,b}) = B'_{a,b}$ for all $a, b \in {\sf{Ball}}(\zeta)$.
Since $\mathsf{height}(B) + 1 \leq \mathsf{height}(A)$, we have the following.
\begin{align*}
8 \zeta \eta  \leq |\ell_A| \leq 8 \zeta \eta + 2\zeta \mathsf{height}(B)       &\leq 8 \zeta \eta + 2\zeta \mathsf{height}(A) \\
8 \zeta \eta  \leq |r_A|    \leq 8 \zeta \eta + 2\zeta (\mathsf{height}(B) + 1) &\leq 8 \zeta \eta + 2\zeta \mathsf{height}(A)
\end{align*}
Thus the length bounds of Equation~\ref{equ-length} are satisfied.

Now assume that $|v| > 2\zeta$.
Again, we set $\ell_A = \ell_B$.
Since $|r_B v| \geq 8\zeta \eta$ we can define  $r_A$ as the suffix of $r_B v$ of length $8\zeta \eta$; that is, $r_B \cdot v = y \cdot r_A$ for some word $y$ of length $|y| = |r_B|+|v|-|r_A| \ge |v| > 2\zeta$.
This satisfies the required bounds on the lengths of $\ell_A$ and $r_A$.

It remains to define the right-hand sides for the variables $A'_{a,b}$ for all $a, b \in {\sf{Ball}}(\zeta)$.
Let us fix $a, b \in {\sf{Ball}}(\zeta)$.
For all $c \in {\sf{Ball}}(\zeta)$ we compute $z = \mathsf{slex}( c y b^{-1})$ and check whether the word
\[
\mathsf{eval}(B'_{a,c}) \cdot z = \mathsf{slex}(a u' c^{-1}) \cdot \mathsf{slex}(c y b^{-1})
\]
is shortlex reduced.
If it is, then it equals $\mathsf{slex}(a u' y b^{-1})$; see Figure~\ref{fig-one-long}.
By Lemma~\ref{lem-quad}, there must be at least one such $c$, for which we define
\[
\rho'(A'_{a,b}) = B'_{a,c} \cdot z
\]
\end{subcase}

\begin{figure}
  \tikzstyle{vertex}=[circle, fill, inner sep=.5pt, minimum size =.5mm ]
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \node[vertex] (a) {} ;
        \node[vertex,  right = 1cm of a] (b) {};
        \node[vertex,  right = 4cm of b] (c) {};
        \node[vertex,  right = 1cm of c] (d) {};
        \node[vertex,  right = 1.5cm of d] (e) {};
        \node[vertex,  left = 1cm of e] (f) {};
        \node[vertex,  above = 1cm of b] (b') {};
        \node[vertex,  above = 1cm of c] (c') {};
        \node[vertex,  above = 1cm of f] (f') {};
        \draw [->](b') edge node[left=-.7mm]{$a$} (b);
        \draw [<-](c) edge node[left=-.7mm]{$c$} (c');
        \draw [<-](f) edge node[right=-.7mm]{$b$} (f');
        \draw [->](a) edge node[below=-.7mm]{$\ell_B$} (b);
        \draw [->, dashed](b) edge node[below=-.7mm]{$u'$} (c);
        \draw [->, dashed](b') edge node[above=-.7mm]{$\mathsf{slex}(a u' c^{-1})$} (c');
        \draw [->](c') edge node[above=-.7mm]{$z$} (f');
        \draw [->](c) edge node[below=-.7mm]{$r_B$} (d);
        \draw [->](d) edge node[above=-.7mm]{} (e);

        \node[vertex,  inner sep=0pt, minimum size =0mm, above = 1.0mm of c] (c'') {};
        \node[vertex,  inner sep=0pt, minimum size =0mm, above = 1.0mm of f] (f'') {};
        \draw [->](c'') edge node[above=-.7mm]{$y$} (f'');

        \node[vertex,  inner sep=0pt, minimum size =0mm, below = 1.0mm of d] (d'') {};
        \node[vertex,  inner sep=0pt, minimum size =0mm, below = 1.0mm of e] (e'') {};
        \draw [->](d'') edge node[below=-.7mm]{$v$} (e'');
  \end{tikzpicture}}}
  \label{fig-one-long}
  \caption{Case~\ref{sub-one-long} from the proof of Lemma~\ref{lem-TSLP-SLP}.
    Again, dashed lines represent words that are given by straight-line programs.}
\end{figure}

\begin{subcase}
Suppose $|u| \leq 16 \zeta \eta + 2\zeta$ and $|v| > 16 \zeta \eta + 2\zeta$.
This dealt with in similar fashion to the previous case.
\end{subcase}

\begin{subcase}
\label{sub-both-short}
Suppose $|u| \leq 16 \zeta \eta + 2\zeta$ and $|v| \leq 16 \zeta \eta+ 2\zeta$.
In this case, we have computed $u$ and $v$ explicitly at a previous stage.
We now distinguish between the cases $|w| \leq 16 \zeta \eta + 2\zeta$ and $|w| > 16 \zeta \eta+ 2\zeta$.
In the first case, we record the word $w$ for later use.
In the second, we factorize $w$ as $w = \ell_A \cdot w' \cdot r_A$ with $|\ell_A| = |r_A| = 8 \zeta \eta$, and thus $|w'| \ge 2\zeta$.
We then explicitly compute, for each $a, b \in {\sf{Ball}}(\zeta)$, the word $\mathsf{slex}(a w' b^{-1})$ and set $\rho'(A'_{a,b})$ equal to it.
This again uses Lemma~\ref{lem-shortlex-reduction}.
\end{subcase}
\end{case}

\begin{case}
\label{case-tether-elim}
Suppose $\rho(A) = B \teth{a, b}$ for $a, b \in {\sf{Ball}}(\zeta)$.
Let $u = \mathsf{eval}(B)$ and $v = \mathsf{eval}(A) = \mathsf{slex}(a u b^{-1})$.
The word $u$ is geodesic by assumption, and $v$ is shortlex reduced by definition.
Let $\eta = \mathsf{depth}_t(B)$.
We have $\mathsf{depth}_t(A) = \eta - 1 \geq 1$.

\begin{subcase}
Suppose $|u| \leq 16 \zeta \eta + 2\zeta$.
Hence, at a previous stage, we explicitly computed the word $u$.
Using Lemma~\ref{lem-shortlex-reduction} we explicitly compute the word $v = \mathsf{slex}(a u b^{-1})$.
The rest of the work divides into cases as $|v|$ is less than or equal to $16 \zeta \eta + 2\zeta$ or is greater.
This is analogous to Case~\ref{sub-both-short} (where $w$ plays the role of $v$).
\end{subcase}

\begin{subcase}
Suppose $|u| > 16 \zeta \eta + 2\zeta$.
At a previous stage we computed words $\ell_B, r_B$ with the following properties.
\begin{itemize}
\item
The prefix and suffix $\ell_B, r_B$ satisfy the length constraint of Equation~\ref{equ-length}.
\item
There is a geodesic word $u'$ of length at least $2 \zeta$ with $u = \ell_B \cdot u' \cdot r_B$.
\end{itemize}
Also, we already defined variables $B'_{c,d}$ for all $c, d \in {\sf{Ball}}(\zeta)$
such that $B'_{c,d}$ produces $z = \mathsf{slex}(c u' d^{-1})$.

We check for all $c,d \in {\sf{Ball}}(\zeta)$ whether
\[
\mathsf{slex}(a \cdot \ell_B \cdot c^{-1}) \cdot z \cdot \mathsf{slex}(d \cdot r_B \cdot b^{-1})
     = \mathsf{slex}(a \cdot \ell_B \cdot c^{-1}) \cdot \mathsf{slex}(c u' d^{-1}) \cdot \mathsf{slex}(d \cdot r_B \cdot b^{-1})
\]
is shortlex reduced.
If it is shortlex reduced then it equals
\[
\mathsf{slex}(a \cdot \ell_B \cdot u' \cdot r_B \cdot b^{-1}) = \mathsf{slex}(a u b^{-1}) = v
\]
Again, see Figure~\ref{fig-tether-elim}.
By Lemma~\ref{lem-quad-two}, there must exist such $c, d \in {\sf{Ball}}(\zeta)$.

Let $s = \mathsf{slex}(a \cdot \ell_B \cdot c^{-1})$ and $t = \mathsf{slex}(d \cdot r_B \cdot b^{-1})$.
By the triangle inequality, these words have length at least $8 \zeta \eta - 2 \zeta$.
Hence we can factorize these words as $s = wx$ and $t = yz$ with
\[
|w| = |z| = 8 \zeta (\eta - 1) = 8\zeta \mathsf{depth}_t(A) \geq 8\zeta
\]
Again, see Figure~\ref{fig-tether-elim}.
The words $x$ and $y$ have length at least $6\zeta$.
We set $\ell_A = w$ and $r_A = z$.
These words satisfy the required bounds on their lengths.
Note that
\[
\mathsf{eval}(A) = \mathsf{slex}(a u b^{-1}) = \ell_A \cdot x \cdot \mathsf{slex}(c u' d^{-1}) \cdot y \cdot r_A
\quad \mbox{and} \quad
|x \cdot \mathsf{slex}(c u' d^{-1}) \cdot y| \geq 12\zeta \geq 2 \zeta
\]

It remains to define the right-hand sides of the variables $A'_{a', b'}$ for all $a', b' \in {\sf{Ball}}(\zeta)$.
(This, in essence, is where we call upon Remark~\ref{rem-double-tether}.)

Fix $a', b' \in  {\sf{Ball}}(\zeta)$.
The lower bounds on the lengths of $w, x, y, z$ allow us to apply Lemma~\ref{lem-quad} to the geodesic quadrilaterals with sides labelled $a, \ell_B, c, wx$ and $d, r_B, b, yz$, respectively.
Note that all of these words have been computed explicitly.
Applying Lemma~\ref{lem-shortlex-reduction}, we compute in polynomial time words $e, f \in {\sf{Ball}}(\zeta)$ and factorizations $\ell_B = w' x'$ and $r_B = y' z'$
such that $a w' =_G w e$, $e x' =_G x c$, $d y' =_G y f$, and $f z' =_G z b$.
Again, see Figure~\ref{fig-tether-elim}.
By the triangle inequality, the words $x'$ and $y'$ must have length at least $4 \zeta$.
Now consider the geodesic quadrilateral with sides labelled $x' u' y'$, $\mathsf{slex}(a' e)$, $\mathsf{slex}(b' f)$, and $\mathsf{slex}(a' e x' u' y' (b' f)^{-1})$.
Note that $|x'|, |y'| \geq 4\zeta$ and $|\mathsf{slex}(a' e)|, |\mathsf{slex}(b' f)| \leq 2\zeta$.
Again applying Lemma~\ref{lem-quad-two} there are $c', d' \in {\sf{Ball}}(\zeta)$ such that the word
\begin{eqnarray*}
\lefteqn{
\mathsf{slex}(a' e x' (c')^{-1}) \cdot \mathsf{eval}_{{\mathcal{G}}'}(B'_{c', d'}) \cdot \mathsf{slex}(d' y' (b'f)^{-1}) =}\\
         && \mathsf{slex}(a' e x' (c')^{-1}) \cdot \mathsf{slex}(c' u' (d')^{-1}) \cdot \mathsf{slex}( d' y' (b' f)^{-1})
\end{eqnarray*}
is shortlex reduced.
Thus the above word is $\mathsf{slex}(a' e \cdot x'  u'  y' \cdot (b' f)^{-1})$.
As before, we can compute such $c', d' \in  {\sf{Ball}}(\zeta)$ in polynomial time.
We finally define the right-hand side of $A'_{a', b'}$ as
\[
\rho'(A'_{a', b'}) = \mathsf{slex}(a' e x' (c')^{-1}) \cdot B'_{c',d'} \cdot \mathsf{slex}(d' y' (b' f)^{-1})
\]
This concludes the definition of the right-hand sides for the variables $A'_{a, b}$.
\end{subcase}
\end{case}

We complete the definition of the straight-line program ${\mathcal{G}}'$ by adding a start variable $S'$ to ${\mathcal{G}}'$ and setting $\rho'(S') = \ell_S \cdot S'_{1, 1} \cdot r_S$.
This ensures $\mathsf{eval}({\mathcal{G}}') = \ell_S \cdot \mathsf{slex}(s') \cdot r_S$, where $s'$ is such that $\ell_S \cdot s' \cdot r_S = \mathsf{eval}({\mathcal{G}})$.
But $\mathsf{eval}({\mathcal{G}})$ is shortlex reduced (since $\rho(S)$ has the form $A \teth{1, 1}$).
Hence $s'$ is also shortlex reduced and we find
\[
\mathsf{eval}({\mathcal{G}}') = \ell_S \cdot \mathsf{slex}(s') \cdot r_S = \ell_S \cdot s' \cdot r_S = \mathsf{eval}({\mathcal{G}})
\]

This concludes the proof of the lemma.
\end{proof}

\begin{figure}[t]
  \tikzstyle{vertex}=[circle, fill, inner sep=.5pt, minimum size =.5mm ]
  \tikzstyle{zero} = [circle, inner sep=0mm]
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \node[vertex] (a) {};
        \node[vertex,  right = 1cm of a] (b) {};
        \node[vertex,  right = 1cm of b] (c) {};
        \node[vertex,  right = 4cm of c] (d) {};
        \node[vertex,  right = 1cm of d] (e) {};
        \node[vertex, right = 1cm of e] (f) {};

        \node[vertex,  above = 1cm of a] (a') {};
        \node[vertex,  above = 1cm of b] (b') {};
        \node[vertex,  above = 1cm of c] (c') {};
        \node[vertex,  above = 1cm of d] (d') {};
        \node[vertex,  above = 1cm of e] (e') {};
        \node[vertex,  above = 1cm of f] (f') {};

        \node[vertex,  above = 1cm of b'] (b'') {};
        \node[vertex,  above = 1cm of c'] (c'') {};
        \node[vertex,  above = 1cm of d'] (d'') {};
        \node[vertex,  above = 1cm of e'] (e'') {};

        \node[zero,  above = 1pt of c] (ca) {};
        \node[zero,  right = 1pt of ca] (car) {};
        \node[zero,  above = 1pt of d] (da) {};
        \node[zero,  left = 1pt of da] (dal) {};

        \draw [->](a) edge node[above=-.7mm]{$w'$} (b);
        \draw [->](b) edge node[above=-.7mm]{$x'$} (c);
        \draw [->, dashed](c) edge node[below=-.7mm]{$u'$} (d);
        \draw [->](d) edge node[above=-.7mm]{$y'$} (e);
        \draw [->](e) edge node[above=-.7mm]{$z'$} (f);

        \draw [->](a') edge node[below=-.7mm]{$w$} (b');
        \draw [->](a') edge node[above=-.7mm]{$\ell_A$} (b');
        \draw [->](b') edge node[below=-.7mm]{$x$} (c');
        \draw [->, dashed](c') edge node[below=-.7mm]{} (d');
        \draw [->](d') edge node[below=-.7mm]{$y$} (e');
        \draw [->](e') edge node[below=-.7mm]{$z$} (f');
        \draw [->](e') edge node[above=-.7mm]{$r_A$} (f');

        \draw [->](b'') edge node[below]{} (c'');
        \draw [->, dashed](c'') edge node[below]{} (d'');
        \draw [->](d'') edge node[below]{} (e'');

        \draw [->](a') edge node[left=-.7mm]{$a$} (a);
        \draw [->](b') edge node[left=-.7mm]{$e$} (b);
        \draw [->](c') edge node[left=-.7mm]{$c$} (c);
        \draw [<-](d) edge node[right=-.7mm]{$d$} (d');
        \draw [<-](e) edge node[right=-.7mm]{$f$} (e');
        \draw [<-](f) edge node[right=-.7mm]{$b$} (f');

        \draw [->](b'') edge node[left=-.7mm]{$a'$} (b');
        \draw [<-](e') edge node[right=-.7mm]{$b'$} (e'');

        \draw [->](c'') to[out=-70,in=70,pos=0.67] node[right=-.7mm] {$c'$} (car);
	\draw [<-](dal) to[out=-250,in=250,pos=0.33] node[left=-.7mm] {$d'$} (d'');

        \node[vertex,  inner sep=0pt, minimum size =0mm, below = .6mm of a] (a''') {};
        \node[vertex,  inner sep=0pt, minimum size =0mm, below = .6mm of c] (c''') {};
        \draw [->](a''') edge node[below=-.7mm]{$\ell_B$} (c''');

        \node[vertex,  inner sep=0pt, minimum size =0mm, below = .6mm of d] (d''') {};
        \node[vertex,  inner sep=0pt, minimum size =0mm, below = .6mm of f] (f''') {};
        \draw [->](d''') edge node[below=-.7mm]{$r_B$} (f''');
  \end{tikzpicture}}}
  \label{fig-tether-elim}
  \caption{ Case~\ref{case-tether-elim} from the proof of Lemma~\ref{lem-TSLP-SLP}.
Again, dashed lines represent words that are given by straight-line programs. }
\end{figure}

The next lemma follows easily from Lemma~\ref{lem-TSLP-SLP}.

\begin{lemma}
\label{lem-TSLP-lengths}
There is a polynomial-time algorithm that, given a geodesic tethered program ${\mathcal{G}}$, computes for every $A$ the length
$|\mathsf{eval}(A)|$.
\end{lemma}

\begin{proof}
By Lemma~\ref{lem-TSLP-SLP}, we can compute for every variable $A$ a straight-line program ${\mathcal{G}}_A$ with $\mathsf{eval}({\mathcal{G}}_A) = \mathsf{slex}(\mathsf{eval}(A))$.
As in Section~\ref{subsec-algo-compressed}, we can compute $|\mathsf{eval}({\mathcal{G}}_A)| = |\mathsf{slex}(\mathsf{eval}(A))| = |\mathsf{eval}(A)|$ in polynomial time.
Here the last equality holds since ${\mathcal{G}}$ is a geodesic program.
\end{proof}

The next lemma generalizes Lemma~\ref{lem-TSLP-SLP} to tether-cut programs.

\begin{lemma}
\label{lem-TCSLP-SLP}
There is a polynomial-time algorithm that, given a geodesic tether-cut program ${\mathcal{G}}$, computes a geodesic straight-line program ${\mathcal{G}}'$ such that $\mathsf{eval}({\mathcal{G}}') = \mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$.
\end{lemma}

\begin{proof}
The idea of the proof is taken from the proof of \ref{thm-hagenah}; see~\cite{Hag00}.
That is, we will eliminate cut operators by pushing them towards smaller variables.
We then appeal to Lemma~\ref{lem-TSLP-SLP} to eliminate tether operators.

Let ${\mathcal{G}} = (V, S, \rho)$ be the input geodesic tether-cut program.
By Lemma~\ref{lem-CNF}, we can assume that ${\mathcal{G}}$ is in Chomsky normal form.
Let $\mu = \mathsf{height}({\mathcal{G}})$.

Consider a variable $A$ such that $\rho(A) = B[:i]$; the case that $\rho(A) = B[i:]$ is dealt with analogously.
We consider variables in order of \emph{increasing} height; so the algorithm is bottom-up.
By induction we may assume that no cut operator occurs in the right-hand side of any variable $C$ with height less than that of $A$.

We now must eliminate the cut operator in $\rho(A)$.
In so doing, we add at most $\mu$ new variables to the tether-cut program.
Moreover the height of the tether-cut program after the cut elimination will still be bounded by $\mu$.
Hence, the final tethered program will have at most $\mu \cdot |V|$ variables.
In addition, every right-hand side of the final program will have length at most $2\zeta + 1$.
This maximum may occur in Case~\ref{sub-near-back}, below.
Thus, its size will be polynomially bounded.

Recall that $\rho(A) = B[:i]$.
We divide the work into cases, depending on the form of $\rho(B)$.

\begin{case_t}
Suppose $\rho(B) = a \in \Sigma$.
If $i = 1$ we redefine $\rho(A) = a$, and if $i = 0$ we redefine $\rho(A) = \varepsilon$.
\end{case_t}

\begin{case_t}
Suppose $\rho(B) = CD$ with $C, D \in V$.
We compute $n_C = |\mathsf{eval}(C)|$ using Lemma~\ref{lem-TSLP-lengths} and with an appeal to the induction hypothesis.
If $i \leq n_C$ then we redefine $\rho(A) = C[:i]$.
If $i > n_C$ then we add a new variable $X$, we define $\rho(X) = D[:i - n_C]$, and we redefine $\rho(A) = CX$.
We then eliminate the new cut operator in $C[:i]$ or in $D[:i-n_C]$ via a top-down sub-routine.
(This is what leads to the quadratic growth of new variables.)
\end{case_t}

\begin{case_t}
Suppose $\rho(B) = C\teth{a, b}$ with $C \in V$ and $a, b \in {\sf{Ball}}(\zeta)$.
Let $u = \mathsf{eval}_{{\mathcal{G}}}(C)$, $v = \mathsf{eval}_{{\mathcal{G}}}(B)$, and $v = v' v''$ with $|v'| = i$.
Thus, we have $\mathsf{eval}_{{\mathcal{G}}}(A) = v'$ and $v = \mathsf{slex}(a u b^{-1})$.
By Lemma~\ref{lem-TSLP-SLP} we can assume that we have straight-line programs for the words $u$ and $v$.

\begin{subcase_t}
\label{sub-near-front}
There exists $c \in {\sf{Ball}}(\zeta)$ and a factorization $a = a' a''$ such that $v' c =_G a'$; see Figure~\ref{fig-near-front}.
Note that this implies that $i = |v'| \leq 2\zeta$.
Hence, we can check in polynomial time whether this case holds by computing the prefix of the compressed word $v$ of length $i$.
We redefine $\rho(A) = v'$.
\end{subcase_t}

\begin{figure}
  \tikzstyle{small} = [circle,draw=black,fill=black,inner sep=.15mm]
  \tikzstyle{zero} = [circle,inner sep=0mm]
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}

        \node[small] (1) {};
        \node[small,  right = 6cm of 1] (2) {};
        \node[small,  above = 1.5cm of 1] (3) {};
        \node[small,  right = 6cm of 3] (4) {};

        \node[zero,  above = .6mm of 3] (3') {};
        \node[zero,  above = .6mm of 4] (4') {};

        \draw [->] (3) to [out=-30, in=-150] node[pos=.08,below=-.5mm]{$v'$}
                                             node[pos=0.2, small] (b) {}
                                             node[pos=.6,below=-.7mm]{$v''$} (4);

        \draw [->](3') to [out=-30, in=-150] node[above=-.7mm]{$v$} (4');

        \draw [->] (3) to node[pos=.25,left=-.7mm]{$a'$}
                          node[pos=0.5, small] (a) {}
                          node[pos=.75,left=-.7mm]{$a''$} (1);

        \draw [<-](2) edge node[right=-.7mm]{$b$} (4);
        \draw [->](1) edge node[above=-.7mm]{$u$} (2);
        \draw [->](a) to [out=0, in=-150] node[below=-.7mm]{$c$} (b);
  \end{tikzpicture}}}
  \caption{ Case~\ref{sub-near-front} in the proof of Lemma~\ref{lem-TCSLP-SLP}. }
  \label{fig-near-front}
\end{figure}

\begin{subcase_t}
\label{sub-near-back}
There exists $c \in {\sf{Ball}}(\zeta)$ and a factorization $b = b'' b'$ such that $v'' b'' =_G c$; see Figure~\ref{fig-near-back}.
As in Case~\ref{sub-near-front} we can check in polynomial time whether this condition holds.
We introduce a new variable $X$, we set $\rho(X) = C \teth{1, b'}$, and we redefine $\rho(A) = X \teth{a, c^{-1}}$.
\end{subcase_t}

\begin{figure}
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \tikzstyle{small} = [circle,draw=black,fill=black,inner sep=.15mm]
        \tikzstyle{zero} = [circle,inner sep=0mm]

        \node[small] (1) {} ;
        \node[small, right = 6cm of 1] (2) {};
        \node[small, above = 1.5cm of 1] (3) {};
        \node[small, right = 6cm of 3] (4) {};

        \node[zero, above = .6mm of 3] (3') {};
        \node[zero, above = .6mm of 4] (4') {};

        \draw [->] (3) to [out=-30, in=-150] node[pos=.4,below=-.7mm] {$v'$} node[pos=0.8, small] (b) {}  node[pos=.92,below=-.8mm]  {$v''$}  (4);
        \draw [->](3') to [out=-30, in=-150] node[above=-.7mm]{$v$} (4');

        \draw [->](3) edge node[left=-.7mm]{$a$} (1);
        \draw [<-] (2) to node[pos=.25,right=-.7mm] {$b'$} node[pos=0.5, small] (a) {}  node[pos=.75,right=-.7mm]  {$b''$}  (4);

        \draw [->](1) edge node[above=-.7mm]{$u$} (2);
        \draw [->](b) to [out=-30, in=180] node[below=-.7mm]{$c$} (a);
  \end{tikzpicture}}}
  \caption{Case~\ref{sub-near-back} in the proof of
    Lemma~\ref{lem-TCSLP-SLP}.}
  \label{fig-near-back}
\end{figure}

\begin{subcase_t}
Neither Case~\ref{sub-near-front} nor Case~\ref{sub-near-back} holds.
In this case, there exists a factorization $u = u' u''$ and $c \in {\sf{Ball}}(\zeta)$ such that $v' c =_G a u'$ and $v'' b =_G c u''$; see Figure~\ref{fig-quad}.
The triangle inequality implies $i - 2 \zeta \leq |u'| \leq i + 2 \zeta$.
We can find such a factorization of $u$ in polynomial time; we note that $j$ lies in $\mathbb{N}$ and satisfies $|i - j| \leq 2\zeta$.
So we find straight-line programs for the polynomially-many words $u' = u[:j]$.
Then we apply Lemma~\ref{lem-TSLP-SLP} and compute for every $c \in {\sf{Ball}}(\zeta)$ a straight-line program for the word $w' = \mathsf{slex}(a u' c^{-1})$.
We have, from Theorem~\ref{thm-hagenah}, a shortlex program for $v'$.
Finally, we check, using Theorem~\ref{thm-plandowski}, whether $v' = w'$.

Hyperbolicity ensures that we will find at least one such $j$ and $c$.
We introduce a new variable $X$, we set $\rho(X) = C[:j]$, and we redefine $\rho(A) = X \teth{a, c}$
We then continue with the elimination of the cut operator in $C[:j]$, as in Case~\ref{sub-near-back}.
\end{subcase_t}

\end{case_t}
This concludes the proof of the lemma.
\end{proof}

Recall our convention: if $w \in \Sigma^*$ is a word then $g_w \in G$ is the corresponding group element.
Thus $g_w$ is a vertex of the Cayley graph $\Gamma = \Gamma(G, \Sigma)$.

\begin{lemma}
\label{lem-small-dist}
There is a polynomial-time algorithm that, given geodesic tether-cut programs ${\mathcal{G}}$ and ${\mathcal{H}}$, determines if $d_\Gamma(g, h) \leq \delta$, where $g = g_{\mathsf{eval}({\mathcal{G}})}$ and $h = g_{\mathsf{eval}({\mathcal{H}})}$.
Moreover, when this holds, the algorithm also finds an element $b \in {\sf{Ball}}(\delta)$ such that $g =_G h b$.
\end{lemma}

\begin{proof}
Let $S$ and $T$ be the start variables of ${\mathcal{G}}$ and ${\mathcal{H}}$, respectively.
For all $b \in {\sf{Ball}}(\delta)$ we produce a new geodesic tether-cut program ${\mathcal{G}}^b$ with $\mathsf{slex}( \mathsf{eval}({\mathcal{G}}) b^{-1})$.
We do this by adding to ${\mathcal{G}}$ a new start variable with right-hand side $S \teth{1, b}$.

We also add to ${\mathcal{H}}$ a new start variable with right-hand side $T \teth{1,1}$.
This ensures that the evaluation of ${\mathcal{H}}^1$ is $\mathsf{slex}( \mathsf{eval}({\mathcal{H}}) )$.
Using Lemma~\ref{lem-TCSLP-SLP} and Theorem~\ref{thm-plandowski} we now check, in polynomial time, if $\mathsf{eval}({\mathcal{G}}^b) = \mathsf{eval}({\mathcal{G}}^1)$.
This is equivalent to $g =_G h b$.
\end{proof}

\subsection{Solving the compressed word problem}

We now prove our main result.
Recall that $\Sigma$ is a symmetric generating set for the hyperbolic group $G$.

\begin{theorem}
\label{thm-SLP-for-shortlex}
There is a polynomial-time algorithm that, given a straight-line program ${\mathcal{G}}$ over $\Sigma$, finds a straight-line program ${\mathcal{H}}$ with evaluation $\mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$.
\end{theorem}

\begin{proof}
By Lemma~\ref{lem-TCSLP-SLP} it suffices to build, in polynomial time, a geodesic tether-cut program ${\mathcal{H}}$ for $\mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$.
We process ${\mathcal{G}}$ from the bottom-up; that is, we consider its variables in order of increasing height.
Set ${\mathcal{G}} = (V, S, \rho)$; applying~\cite[Proposition~3.8]{Loh14}, we may assume that ${\mathcal{G}}$ is in Chomsky normal form.
We build a new tether-cut program ${\mathcal{G}}' = (V', S', \rho')$ over $\Sigma$; here $V'$ is a copy of $V$ and $S' \in V'$ is the variable corresponding to $S$.
Our induction hypotheses for $A$ in $V$ are as follows.
\begin{itemize}
\item
The height of $A'$ in ${\mathcal{G}}'$ is at most that of $A$ in ${\mathcal{G}}$.
\item
The evaluation of $A'$ equals $\mathsf{slex}(\mathsf{eval}(A))$.
\end{itemize}

In the base cases we have $\rho(A) = a \in \Sigma$.  Here we set $\rho'(A') = \mathsf{slex}(a)$.

In the inductive step we have $\rho(A) = BC$.
Since $B$ and $C$ have smaller height than $A$ they satisfy the induction hypotheses.
Set
\[
u = \mathsf{slex}(\mathsf{eval}(B)) = \mathsf{eval}(B')
\quad \mbox{and} \quad
v = \mathsf{slex}(\mathsf{eval}(C)) = \mathsf{eval}(C')
\]
By Lemma~\ref{lem-TCSLP-SLP} we can transform the tether-cut programs with start variables $B'$ and $C'$ into geodesic straight-line programs.
Using these, we compute the lengths $m = |u|$ and $n = |v|$.
If one or both of these have length zero then we accordingly take $\rho'(A') = C'$ or $\rho'(A') = B'$ or $\rho'(A') = \varepsilon$.
We now assume that $m$ and $n$ are both non-zero.
Breaking symmetry, we assume that  $m \leq n$.

Let $P$ be the path starting at $1_G$, ending at $u$, and labelled by $u$.  Similarly, let $Q$ be the the path starting at $u$, ending at $uv$, and labelled by $v$.  Finally, let $R$ be the path starting at $1_G$, ending at $uv$, and labelled by $\mathsf{slex}(uv)$.
See Figure~\ref{fig-cutting-off-peak}.  The path $\bar{P}$, the reverse of $P$, is labelled by $u^{-1}$.  Applying Remark~\ref{rem-inverse} we invert the geodesic straight-line program for $u$ to give a straight-line program for $u^{-1}$.  Using Lemma~\ref{lem-small-dist} we can check whether or not
\[
d_\Gamma(\bar{P}(m), Q(m)) \leq \delta
\]
We break into cases accordingly.

\begin{case_s}
\label{case-end-close}
Suppose that $d_\Gamma(\bar{P}(m), Q(m)) \leq \delta$.
We compute, again using Lemma~\ref{lem-small-dist}, a word $a$ of length at most $\delta$ such that $a =_G u v[:m]$.
See the left-hand side of Figure~\ref{fig-cutting-off-peak}.
In this case we set $\rho'(A') = C'[m:] \teth{a, 1}$.
\end{case_s}

\begin{case_s}
\label{case-end-far}
Suppose that $d_\Gamma(\bar{P}(m), Q(m)) > \delta$.
Using binary search, we compute an integer $k \in [0, m - 1]$ such that
\[
d_\Gamma(\bar{P}(k), Q(k)) \leq \delta
\quad \mbox{and} \quad
d_\Gamma(\bar{P}(k + 1), Q(k + 1)) > \delta
\]
Here are the details of the binary search.
We store an interval $[p, q] \subseteq [0, m]$ such that
\begin{itemize}
\item
$p < q$,
\item
$d_\Gamma(\bar{P}(p), Q(p)) \leq \delta$, and
\item
$d_\Gamma(\bar{P}(q), Q(q)) > \delta$.
\end{itemize}
We begin with $p = 0$ and $q = m$.
We stop when $q = p + 1$.
In each iteration, we compute $r = \ceiling{(p + q)/2}$ and check, using Lemma~\ref{lem-small-dist}, whether
\[
d_\Gamma(\bar{P}(r), Q(r)) \leq \delta
\quad \mbox{or} \quad
d_\Gamma(\bar{P}(r), Q(r)) > \delta
\]
In the first case we set $p = r$ and do not change $q$; in the second case we set $q = r$ and do not change $p$.
In each iteration the size of the interval $[p, q]$ is roughly halved.
Thus the binary search halts after $O(\log(m))$ iterations; this is polynomial in the input size.
In addition to the final position $k$, we record a word $a \in {\sf{Ball}}(\delta)$ that labels a path from $\bar{P}(k)$ to $Q(k)$.
Let $j = k + 1$.

Recall that $R$ is the path from $\bar{P}(m)$ to $Q(n)$ labelled by $\mathsf{slex}(uv)$.
By Lemma~\ref{lem-thin-triangle} there exist $i_P \leq i_Q$ such that
\[
d_\Gamma( \bar{P}(j), R(i_P)) \leq \delta
\quad \mbox{and} \quad
d_\Gamma( Q(j), R(i_Q)) \leq \delta
\]
For all pairs $b, c \in {\sf{Ball}}(\delta)$ we compute the word
\[
s = \mathsf{slex}( b \cdot u[m - j] \cdot a \cdot v[k] \cdot c^{-1})
\]
For each of these, we must check if the word
\begin{equation}
\label{lower-triangle-side}
\mathsf{slex}(u[ : m - j] \cdot b^{-1}) \cdot s \cdot \mathsf{slex}( c \cdot v[j : ] )
\end{equation}
is shortlex reduced; if so, it equals $\mathsf{slex}(uv)$.
This step can be done using Lemma~\ref{lem-shortlex-regular} and using the given geodesic tether-cut programs for $u$ and $v$.
From these we obtain geodesic tether-cut programs for $\mathsf{slex}( u[ : m - j] \cdot b^{-1})$ and $\mathsf{slex}( c \cdot v[j : ] )$.  We then use Lemma~\ref{lem-TCSLP-SLP} to transform these into equivalent straight-line programs.

Lemma~\ref{lem-thin-triangle} ensures that that we will find a pair $b, c \in {\sf{Ball}}(\delta)$ such that the word in \eqref{lower-triangle-side} is shortlex reduced.
Using the first such pair we find, we set
\[
\rho'(A) = ( B'[ : m - j] \teth{1, b}) \cdot s \cdot (C' [j : ] \teth{c, 1} )
\]
\end{case_s}

This concludes the proof of the theorem.
\end{proof}

\begin{figure}
  \centering{
    \scalebox{1}{
      \begin{tikzpicture}
        \tikzstyle{small} = [circle,draw=black,fill=black,inner sep=.15mm]
        \tikzstyle{zero} = [circle,inner sep=0mm]

        \node[small] (1) {} ;
        \node[zero, above = 0.3mm of 1] (1') {} ;
        \node[small,  right = 1.7cm of 1] (1a) {} ;
        \node[small,  right = 2.3cm of 1] (1b) {} ;
        \node[small,  right = 4cm of 1] (2) {} ;
        \node[zero, above = 0.3mm of 2] (2') {} ;
        \node[small,  above right = 2.5cm and 2cm of 1] (3) {} ;
        \node[zero, left = 0.3mm of 3] (3') {} ;
        \node[zero, right = 0.3mm of 3] (3'') {} ;

        \draw [->] (1) to (1a) ;
        \draw [->] (1a) to node[below=-.7mm] {$s$} (1b) ;
        \draw [->] (1b) to (2) ;

        \draw [-] (1) to [out=5, in=-95] node[pos=0.45, small] (2a) {}  node[pos=0.55, small] (2b) {}  (3);
        \draw [->] (1') to [out=5, in=-95] node[above left =-.7mm and -.7mm] {$u$} (3');
        \draw [-] (3) to [out=-85, in=175] node[pos=0.45, small] (3a) {}  node[pos=0.55, small] (3b) {}  (2);
        \draw [->] (3'') to [out=-85, in=175] node[above right =-.7mm and -.7mm] {$v$} (2');
        \draw [->] (2b) to node[above=-.7mm] {$a$} (3a) ;
        \draw [<-] (2a) to node[left=-.7mm] {$b$} (1a) ;
        \draw [->] (1b) to node[right=-.7mm] {$c$} (3b) ;

        \node[small, above left = 1cm and 5cm of 1] (4) {} ;
        \node[small,  above right = 1.5cm and 1cm of 4] (5) {} ;
        \node[zero, right = 0.3mm of 5] (5') {} ;
        \node[small,  below right = 1cm and 2cm of 4] (6) {} ;
        \node[zero, above = 0.3mm of 6] (6') {} ;
        \draw [->] (4) to [out=5, in=-95] node[above left = -.7mm and -.3mm] (c) {$u$}  (5);

        \draw [-] (5) to [out=-85, in=175] node[pos=0.457, small] (56) {}  (6);
        \draw [->] (5') to [out=-85, in=175] node[above right =-.7mm and -.7mm] {$v$} (6');
        \draw [->] (4) to node[below=-.7mm, pos=0.6] {$a$} (56) ;
        \draw [->] (4) to [out=-40, in=180]  (6);

  \end{tikzpicture}}}
  \caption{Case~\ref{case-end-close} (left) and~\ref{case-end-far} (right) from the proof of Theorem~\ref{thm-SLP-for-shortlex}.}
  \label{fig-cutting-off-peak}
\end{figure}

Theorem~\ref{thm-SLP-for-shortlex} now solves the compressed word problem.

\begin{corollary}
\label{coro-CWP-hyperbolic}
The compressed word problem for a hyperbolic group can be solved in polynomial time.
\end{corollary}

\begin{proof}
Suppose that ${\mathcal{G}}$ is the given compressed word.
Note that $\mathsf{eval}({\mathcal{G}}) \in \Sigma^*$ represents $1_G$ if and only if $\mathsf{slex}(\mathsf{eval}({\mathcal{G}})) = \varepsilon$.
This, in turn, happens if and only if $\mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$ has length zero.
Since Theorem~\ref{thm-SLP-for-shortlex} gives a straight-line program ${\mathcal{G}}'$ for $\mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$, we are done.
\end{proof}

\section{Further compressed decision problems}

\subsection{Compressed order problem}
\label{sec-order}

Suppose that $G$ is a group.
Suppose that $\Sigma$ is a finite, symmetric generating set for $G$.
For any $g \in G$ we define the \emph{order} of $g$ to be the smallest positive integer $k$ so that $g^k = 1_G$.
If there is no such $k$ we define the order to be infinity.
We define the \emph{compressed order problem} as follows.

\begin{description}
\item[Input] Straight-line program ${\mathcal{G}}$ over $\Sigma$.
\item[Output] The order of the group element $\mathsf{eval}({\mathcal{G}})$.
\end{description}

As a consequence of Corollary~\ref{coro-CWP-hyperbolic} we have the following result.

\begin{corollary}
\label{coro-order}
Let $G$ be a hyperbolic group.
Then the compressed order problem for $G$ can be solved in polynomial time.
\end{corollary}

\begin{proof}
Let ${\mathcal{G}}$ be the given compressed word.
Since $G$ is hyperbolic, it has only finitely many conjugacy classes of finite subgroups~\cite[Theorem 6.8.4]{HRR2017}.
Thus there is a bound $c = c(G)$ on the size of its finite cyclic subgroups.
Thus the order of any element $g \in G$ belongs to $\{1, \ldots, c\} \cup \{\infty\}$.

To compute the order of $\mathsf{eval}({\mathcal{G}})$ it suffices to check whether $\mathsf{eval}({\mathcal{G}})^k =_G 1_G$ for some integer $k$ in the range $\{1, \ldots, c\}$.
Proposition~\ref{prop-power} gives us the desired compressed word and Corollary~\ref{coro-CWP-hyperbolic} checks it, both in polynomial time.
\end{proof}

\subsection{The compressed (simultaneous) conjugacy and compressed centralizer problems}
\label{sec-conjugacy}

Suppose that $G$ is a group.
Suppose that $\Sigma$ is a finite, symmetric generating set for $G$.
For group elements $g, h \in G$ we have the standard abbreviation $g^h = h^{-1} g h$.
If ${\mathcal{L}} = (g_1, \ldots, g_k)$ is a finite list of group elements then we write ${\mathcal{L}}^h = (g_1^h, \ldots, g_k^h)$.
We extend these definitions to words over $\Sigma$ in the obvious way.

\subsection{The problems}

The \emph{compressed conjugacy problem} for $G$ is the following.

\begin{description}
\item[Input]
Straight-line programs ${\mathcal{G}}$ and ${\mathcal{H}}$ over $\Sigma$.
\item[Question]
Do $\mathsf{eval}({\mathcal{G}})$ and $\mathsf{eval}({\mathcal{H}})$ represent conjugate elements in $G$?
\end{description}

If ${\mathcal{L}}$ is a list of straight-line programs over $\Sigma$, then we define $\mathsf{eval}({\mathcal{L}})$ to be the corresponding list of evaluations.
We now define the \emph{compressed simultaneous conjugacy problem} for $G$.
\begin{description}
\item[Input]
Finite lists ${\mathcal{L}} = ({\mathcal{G}}_1,\ldots,{\mathcal{G}}_k)$ and ${\mathcal{M}} = ({\mathcal{H}}_1,\ldots,{\mathcal{H}}_k)$ of straight-line programs over $\Sigma$.
\item[Question]
Are $\mathsf{eval}({\mathcal{L}})$ and $\mathsf{eval}({\mathcal{M}})$ conjugate lists in $G$?
\end{description}

In the case when the answer to either of these questions is positive, we might also want to compute a straight-line program for an element that conjugates $\mathsf{eval}({\mathcal{G}})$ to $\mathsf{eval}({\mathcal{H}})$ or $\mathsf{eval}({\mathcal{L}})$ to $\mathsf{eval}({\mathcal{M}})$.

The \emph{compressed centralizer problem} for $G$ is the following computation problem.

\begin{description}
\item[Input]
A finite list ${\mathcal{L}} = ({\mathcal{G}}_1, \ldots, {\mathcal{G}}_k)$ of straight-line programs over $\Sigma$.
\item[Output]
A finite list ${\mathcal{M}} = ({\mathcal{H}}_1, \ldots, {\mathcal{H}}_l)$ such $\mathsf{eval}({\mathcal{M}})$ generates the intersection of the centralizers of the elements $\mathsf{eval}({\mathcal{L}})$.
\end{description}

Note that this intersection is in fact the centralizer of the subgroup generated by the elements $\mathsf{eval}({\mathcal{L}})$.
When the desired centralizer is not finitely generated, by convention the problem has no solution.

\subsection{The proofs}

A linear-time algorithm for solving the conjugacy problem in a hyperbolic group $G$ is described in~\cite[Section~3]{EpsteinH06}.  This was generalized in~\cite{BuckleyHolt13} to linear-time algorithms for the (uncompressed) simultaneous conjugacy, and the centralizer, problems.
We will show that essentially the same algorithms can be used to solve the compressed (simultaneous) conjugacy problem and the compressed centralizer problem, in polynomial time.

We deal with the compressed conjugacy problem in Section~\ref{sec-conjugacy-1}.
Building on that, and making the special assumption that one of the input elements has infinite order, we solve the compressed simultaneous conjugacy problem and the compressed centralizer problem in Section~\ref{sec-infinite-order}.
Finally, we deal with the case that all input group elements have finite order in Section~\ref{sec-finite-order}.

\subsubsection{Compressed conjugacy problem}
\label{sec-conjugacy-1}

We now have the following.

\begin{theorem}
\label{thm-comp-conj}
Let $G$ be a hyperbolic group.
Then the compressed conjugacy problem in $G$ is polynomial time.
\end{theorem}

\begin{proof}
The input consists of two straight-line programs ${\mathcal{G}}$ and ${\mathcal{H}}$; we wish to test if $u = \mathsf{eval}({\mathcal{G}})$ and
$v = \mathsf{eval}({\mathcal{H}})$ are conjugate.
To do this we essentially use the conjugacy algorithm from~\cite[Theorem~1.1]{EpsteinH06}, applied to the words $u$ and $v$.
We will describe our modification of their algorithm, step-by-step, in the following.

Our description of each step consists of two parts.
The first describes operations relating to the words $u$ and $v$; the second explains how we effect these operations in polynomial time using only the straight-line programs ${\mathcal{G}}$ and ${\mathcal{H}}$.
All assertions that we make in the uncompressed setting are justified in~\cite{EpsteinH06}.
All corresponding assertions are then justified again, in the compressed setting, using the work in previous sections of this paper.

Let $\delta$ be a positive integer that serves as a thinness constant for the Cayley graph $\Gamma = \Gamma(G, \Sigma)$; see Section~\ref{sec-hyp}.
We define constants $L = 34\delta + 2$ and $K = 17(2L + 1)/7$; see \cite[pages~298]{EpsteinH06}.

A word $w \in \Sigma^*$ is said to be \emph{shortlex straight} if, for all non-negative powers $k$, the word $w^k$ is shortlex reduced.
Applying Lemma~\ref{lem-shortlex-regular} and Proposition~\ref{prop-fsa-2} we can determine, in polynomial time, if a given compressed word ${\mathcal{G}}$ is shortlex straight.

In the preprocessing stage, we make a look-up table of all pairs of shortlex reduced words of length at most $K$ that are conjugate in $G$.

\begin{step}
\label{step-slex}
We replace $u$ and $v$ by $\mathsf{slex}(u)$ and $\mathsf{slex}(v)$.

By Theorem~\ref{thm-SLP-for-shortlex} we can replace, in polynomial time, the programs ${\mathcal{G}}$ and ${\mathcal{H}}$ by straight-line programs for $\mathsf{slex}(\mathsf{eval}({\mathcal{G}}))$ and $\mathsf{slex}(\mathsf{eval}({\mathcal{H}}))$, respectively.
\end{step}

\begin{step}
\label{step-rotate}
For a word $w$, we define $w_C = w_R w_L$, where $w = w_L w_R$ with $|w_L| \leq |w_R| \leq |w_L| + 1$.
Replace $u$ by $\mathsf{slex}(u_C)$ and $v$ by $\mathsf{slex}(v_C)$.

Using cut operators and Theorem~\ref{thm-SLP-for-shortlex} we can make the corresponding substitutions on ${\mathcal{G}}$ and ${\mathcal{H}}$.
\end{step}

\begin{step}
\label{step-short}
If $|u|, |v| \leq K$ then use the look-up table to test for conjugacy of $u$ and $v$.
Otherwise, at least one of the words, $u$ say, satisfies $|u| \geq K > 2L + 1$.
If $|v| < 2L + 1$ then $u$ and $v$ are not conjugate~\cite[Section~3.1]{EpsteinH06}, and we return false.
We assume from now on that $|u|, |v| \geq 2L + 1$.

For the compressed conjugacy problem, if $|\mathsf{eval}({\mathcal{G}})|, |\mathsf{eval}({\mathcal{G}})| \leq K$ then we can compute $\mathsf{eval}({\mathcal{G}})$ and $\mathsf{eval}({\mathcal{H}})$ explicitly.
We then proceed as in the uncompressed setting.
\end{step}

\begin{step}
\label{step-straight}
There exists a group element $g \in {\sf{Ball}}(4\delta)$ and a positive integer $m$, of size at most $|{\sf{Ball}}(4 \delta)|^2$, such that the shortlex reduction of $g^{-1} u^m g$ is shortlex straight~\cite[Section~3.2]{EpsteinH06}.
To find such, for every pair $(g, m)$ of at most those sizes, we replace $u$ by $\mathsf{slex}(g^{-1}ug)$ and test $z = \mathsf{slex}(u^m)$ to see if it is shortlex straight.

Using Proposition~\ref{prop-fsa-2}, we can perform the corresponding operations with ${\mathcal{G}}$.  Thus we find $g$ and $m$ and also find a straight-line program ${\mathcal{G}}'$ with $\mathsf{eval}({\mathcal{G}}') = z$.
\end{step}

\begin{step}
\label{step-power}
We now test for the following necessary (but not sufficient) property for
the conjugacy of $u$ and $v$: is $v^m$ conjugate to $z$?
We decide this as follows.
For all $h \in {\sf{Ball}}(6\delta)$,
we compute $v_h = \mathsf{slex}(hv^mh^{-1})$, and then test whether $v_h$ is a rotation of $z$.
If this fails for all $h$, then $v^m$ and $z =_G u^m$ are not conjugate~\cite[Section~3.3]{EpsteinH06}.
But then, $u$ and $v$ are not conjugate,  so we may stop and return false.

Otherwise, we find $h$ and $v_h$ with this property.
Let $z_1$ be a prefix of $z$ such that $z =_G z_1 h v^m h^{-1} z_1^{-1}$.
We replace $v$ by $\mathsf{slex}(z_1 h v h^{-1} z_1^{-1})$.
Now we have $v^m =_G u^m =_G z$.
From this we get that every $g \in G$ with $g^{-1} u g =_G v$ belongs to the centralizer $C_G(z)$ of $z$ in $G$.
In particular, $u$ and $v$ are conjugate in $G$ if and only if they are conjugate in  $C_G(z)$.

Using Corollary~\ref{coro-cyclic-conj} we can do the corresponding calculations with ${\mathcal{H}}$ and ${\mathcal{G}}'$.
Checking whether $v_h$ is a rotation of $z$ can be accomplished in polynomial time by the first statement of Corollary~\ref{coro-cyclic-conj}; the second statement allows us to compute in polynomial time a straight-line program for
$z_1$.
\end{step}

\begin{step}
\label{step-root}
Find the shortest prefix $y$ of $z$ that is a \emph{root} of $z$: that is, there is an $\ell \geq 1$ so that $z = y^\ell$.
We do that by finding the second occurrence of the substring $z$ in the word $z^2$.

To find the root of $\mathsf{eval}({\mathcal{G}}')$, we form $({\mathcal{G}}')^2$ and appeal to Theorem~\ref{thm-pattern-matching}.
We then build a straight-line program ${\mathcal{G}}''$ with $\mathsf{eval}({\mathcal{G}}'') = y$ using cut operators and Theorem~\ref{thm-hagenah}.
\end{step}

\begin{step}
\label{step-candidates}
For each $h \in {\sf{Ball}}(2\delta)$, compute $\mathsf{slex}(h z h^{-1})$ and test whether it is a rotation of $z$.
If so, find a prefix $z_h$ of $z$ with $hzh^{-1} =_G z_h^{-1} z z_h$, and compute and store  $\mathsf{slex}(z_h \cdot h)$ (which lies in $C_G(z)$) in a list $C_z$.
Then $|C_z| \leq J = |{\sf{Ball}}(2\delta)|$.

Corollary~\ref{coro-cyclic-conj} allows us to do the corresponding calculations with ${\mathcal{G}}'$.
We obtain a list of straight-line programs that evaluate to the words in the list $C_z$.
\end{step}

\begin{step}
\label{step-check}
For each $n$ with $0 \leq n \leq (J-1)!$ and for each $z' \in C_z$, let $g = y^n z'$.
Test if $u =_G gvg^{-1}$.
If so, then return true (and a conjugating element).
If not, then return false because $u$ and $v$ are not conjugate~\cite[Section~3.4]{EpsteinH06}.

We can perform corresponding operations on the straight-line programs.
\end{step}

This concludes our description of a polynomial-time algorithm for the compressed conjugacy problem.  The correctness proof is identical to that in~\cite[Section~3]{EpsteinH06}
\end{proof}

\subsubsection{Compressed simultaneous conjugacy and centralizers: the infinite order case}
\label{sec-infinite-order}

We now turn to the following.

\begin{theorem}
\label{thm-compcp}
Let $G$ be a hyperbolic group.
Then the compressed simultaneous conjugacy problem for $G$ can be solved in polynomial time.
Moreover, if the two input lists are conjugate, then we can compute a straight-line program for a conjugating element in polynomial time.
\end{theorem}

\begin{theorem}
\label{thm-comp-central}
Let $G$ be a hyperbolic group.
Then the compressed centralizer problem for $G$ can be solved in polynomial time.
\end{theorem}

The input now consists of two lists ${\mathcal{L}} = ({\mathcal{G}}_1,\ldots,{\mathcal{G}}_k)$ and ${\mathcal{M}} = ({\mathcal{H}}_1,\ldots,{\mathcal{H}}_k)$ of straight-line programs over the alphabet $\Sigma$.
For the compressed centralizer problem we assume that ${\mathcal{L}} = {\mathcal{M}}$.
For all $i$ we take $u_i = \mathsf{eval}({\mathcal{G}}_i)$ and $v_i = \mathsf{eval}({\mathcal{H}}_i)$.

By Corollary~\ref{coro-order} we can check in polynomial time whether some $u_i$ has infinite order.
As in~\cite{BuckleyHolt13} we begin, in this section, by assuming that at least one of the $u_i$ has infinite order.
Reordering the lists in the same way, as needed, we may assume that $u_1$ has infinite order.
If $v_1$ does not have infinite order we are done.

The conjugacy testing algorithm proceeds as follows.  We first repeatedly replace the elements in ${\mathcal{L}}$ by conjugates, using a common conjugating element.
This culminates in a check for a conjugating element which must lie in an explicit finite set.
In each replacement, straight-line programs are known for the conjugating element.
By keeping track of these, we can find (if the lists are conjugate) an overall conjugating element for the original input.
We omit further details regarding this overall conjugating element.

We proceed by carrying out the eight steps of the algorithm of Section~\ref{sec-conjugacy-1} as applied to $u_1$ and $v_1$.
If they are not conjugate we are done.
Suppose that they are conjugate.
In this case we record the programs for the words $z$ and $y$ produced by Steps~\ref{step-power} and~~\ref{step-root}.  We also record the list (of straight-line programs) $C_z$ given in Step~\ref{step-candidates}.
The overall algorithm also gives us a straight-line program for an element $g \in G$ with $u_1^g =_G v_1$.
The algorithm also replaced $u_1$ and $v_1$ by conjugates in some of the steps; we make the corresponding replacements to the other elements of ${\mathcal{L}}$ and ${\mathcal{M}}$.
By replacing each $u_i$ by its conjugate under $g$, we may now assume that $u_1 = v_1$.

Thus we have reduced the problem to the following.
Assuming that $u_1 = v_1$ and that $u_1$ has infinite order, we must decide if there is $g \in C_G(u_1)$ with $u_i^g =_G v_i$ for $2 \leq i \leq k$.   We are also given $z$; thus $u_1^m =_G v_1^m =_G z$ and $z$ is shortlex straight element $z$ and $m \geq 1$.
We are also given $y$ with $z = y^\ell$ and for maximal $\ell \geq 1$.

In~\cite[Section~3.4]{EpsteinH06} it is shown that all elements $g \in C_G(z)$ have the form $g =_G y^n z'$, for some $n \in \mathbb{Z}$ and $z' \in C_z$, where $C_z$ is the list given above.
So the same applies to any $g \in C_G(u_1) \subseteq C_G(z)$.

We now try each $z' \in C_z$ in turn.  Replacing each $v_i$ by $z' v_i (z')^{-1}$, the problem reduces to the following:
is there some $n \in \mathbb{Z}$ such that $u_i^{y^n} =_G v_i$ for $1 \leq i \leq k$?

To solve this problem, we apply~\cite[Proposition~24]{BuckleyHolt13} to each pair $u_i, v_i$ in turn.
For each $i$, there are three possibilities.
\begin{enumerate}
\item[(i)]
there exist $0 \leq r_i < t_i \leq |{\sf{Ball}}(2\delta)|$ such that $u_i^{y^j} =_G v_i$ if and only if $j \equiv r_i \bmod t_i$;
\item[(ii)]
there is a unique $r_i \in \mathbb{Z}$ with $u_i^{y^{r_i}} =_G v_i$, where $|r_i|$ is bounded by a linear function of $|u_i|$ and $|v_i|$; or
\item[(iii)]
there is no $r_i \in \mathbb{Z}$ with $u_i^{y^{r_i}} =_G v_i$.
\end{enumerate}
The proof of~\cite[Proposition~24]{BuckleyHolt13} provides an algorithm for determining which case applies, and for finding $r_i, t_i$ in cases (i) and (ii).
This involves calculating a number of powers $u_i^n$, $v_i^n$, and $y^n$ for integers $n$ such that $|n|$ is bounded by a linear function of $|u_i|$ and $|v_i|$, and where the number of powers that need to be calculated is bounded by a constant.
So we can perform these calculations in polynomial time with straight-line programs by Proposition~\ref{prop-power}.

After performing this calculation for each $i$ with $1 \leq i \leq k$, the conjugacy problem for the lists reduces to solving some modular linear equations involving the integers $r_i$ and $t_i$, as described in~\cite[Section~3.4]{BuckleyHolt13}.
Since the $r_i$ and $t_i$ in case (i) are bounded  by a constant and, for $r_i$ in case (ii), $\log |r_i|$ is bounded by a linear function of the size of the straight-line programs representing $u_i$ and $v_i$, these equations can be solved in polynomial time using standard arithmetical operations on the binary representations of $r_i$ and $t_i$.  This completes our discussion of the compressed simultaneous conjugacy problem in the case where there is a list element of infinite order.

For the compressed centralizer problem, we are in the same situation but with $v_i = u_i$ for all $i$.
We perform the same calculations as above, but we do them for every $z' \in C_z$.
If there are solutions, then we find them by solving modular equations.
The set of solutions we find now generates the centralizer.
This completes our discussion of the compressed centralizer problem in the case where there is a list element of infinite order.

\subsubsection{Compressed simultaneous conjugacy and centralizers: the finite order case}
\label{sec-finite-order}

Here we continue the proofs of Theorems~\ref{thm-compcp} and~\ref{thm-comp-central}.
We now consider the case where all of the $u_i$ (in the list $\mathsf{eval}({\mathcal{L}})$) have finite order.
We now follow~\cite[Section~4]{BuckleyHolt13}.
No new complications arise when applying those methods to lists of straight-line programs.
Indeed, some steps become easier because we are only interested in achieving polynomial, rather than linear, time.

We follow the steps of the algorithm described in~\cite[Section~4.5]{BuckleyHolt13}.
We deal with the conjugacy and centralizer problems together; the two lists are taken to be equal for the centralizer calculation.
At this stage we have already verified that all of the $u_i$ and $v_i$ have finite order.
Furthermore all of the words are shortlex reduced.
By deleting programs, we can assume that the list $u_1, \ldots, u_k$, and likewise the list $v_1, \ldots, v_k$, has no duplicates.
Thus the $u_i$ represent distinct group elements, as do the $v_i$.

Let $n = \min\{ |{\sf{Ball}}(2\delta)|^4 + 1, k \}$.
We consider the prefix sublists $\mathsf{eval}({\mathcal{L}}') = (u_1, \ldots, u_n)$ and $\mathsf{eval}({\mathcal{M}}') = (v_1, \ldots, v_n)$.
We apply the function \textsc{ShortenWords} from~\cite[Section~4.2]{BuckleyHolt13} to the lists ${\mathcal{L}}'$ and ${\mathcal{M}}'$.
This function applies $\mathsf{slex}$ to a number of words; this number is bounded above by $n^2$.
Each word is a concatenation (of length at most $n + 2$) of words either from the lists ${\mathcal{L}}'$ or ${\mathcal{M}}'$, or of words previously calculated during this process.
These operations can be executed in polynomial time when working with straight-line programs.
Since there is an absolute bound $|{\sf{Ball}}(2\delta)|^4 + 1$ on the lengths of ${\mathcal{L}}'$ and ${\mathcal{M}}'$, the complete application of \textsc{ShortenWords} to each list takes place in polynomial time.

\textsc{ShortenWords} has two possible outcomes.
In the first it finds a product $u_r \cdot u_{r+1} \cdots u_s$ of elements of ${\mathcal{L}}'$ with infinite order.
This reduces the problem to the case dealt with in Section~\ref{sec-infinite-order}.

In the second possible outcome, \textsc{ShortenWords} replaces ${\mathcal{L}}'$ and ${\mathcal{M}}'$ by conjugates and then calculates lists ${\mathcal{L}}'' = (u_1', \ldots, u_n')$ and ${\mathcal{M}}'' = (v_1', \ldots, v_n')$ with $|u_i'|$ and $|v_i'|$ bounded by a constant, and such that ${\mathcal{L}}^g = {\mathcal{M}}$ if and only if $({\mathcal{L}}'')^g = {\mathcal{M}}''$.

We now test in time $O(1)$ (using our precomputed look-up table) whether there exists $g \in G$ with
\[
(u_1', \ldots, u_n')^g = (v_1', \ldots, v_n')
\]
If so, we replace $(u_1,\ldots,u_k)$ by $(u_1,\ldots,u_k)^g$ and thereby assume that $u_i=v_i$ for $1 \leq i \leq n$.
For the centralizer problem, methods are described in~\cite[Proposition~2.3]{GerstenShort91} of finding a generating set of the
centralizer of any quasiconvex subgroup of any biautomatic group; finitely generated subgroups of hyperbolic groups satisfy these
conditions.
Since they need only be applied to words of bounded length their complexity does not matter - indeed, we could precompute all such centralizers.

This completes the proof in the case $n = k$.
In the case $k > n$, it is proved in~\cite[Corollary~30]{BuckleyHolt13} that the centralizer $C$ of the subgroup $\subgp{u_1, \ldots, u_n}$ is finite, and that the elements of $C$ have lengths bounded by a constant.
So we can compute the elements of $C$ explicitly (in time $O(1)$).
Then we simply need to check whether any $g \in C$ satisfies
\[
(u_{n + 1}, \ldots, u_k)^g = (v_{n + 1}, \ldots, v_k)
\]
This completes the proofs of Theorems~\ref{thm-compcp} and~\ref{thm-comp-central}. \qed

\subsection{Compressed knapsack}

In this final section, we prove the following.

\begin{theorem}
\label{thm-knapsack-hyp}
If $G$ is an infinite hyperbolic group then the compressed knapsack problem for $G$ is $\NP$--complete.
\end{theorem}

As above, fix $G$ a finitely generated group.  Fix as well a finite symmetric generating set $\Sigma$.
A \emph{knapsack expression} over $\Sigma$ is a regular expression of the form $E = u^{-1} u_1^* u_2^* \cdots u_k^*$ with $k \geq 0$ and $u_i \in \Sigma^*$.
The \emph{length} of $E$ is defined to be  $|E| = |u| + \sum_{i = 1}^k |u_i|$.
A \emph{solution} for $E$ is a tuple $(n_1, n_2, \ldots, n_k) \in \mathbb{N}^k$ of natural numbers such that $u =_G u_1^{n_1} u_2^{n_2} \cdots u_k^{n_k}$.

The \emph{knapsack problem} for $G$, over $\Sigma$, is the following.
\begin{description}
\item[Input] A knapsack expression $E$ over $\Sigma$.
\item[Question] Does $E$ has a solution?
\end{description}
In \cite[Theorem~6.1]{MyNiUs14} it was shown that the knapsack problem for a hyperbolic group can be solved in polynomial time.
A crucial step in the proof for this fact is the following result, which is of independent interest.

\begin{theorem}[\mbox{\cite[Theorem~6.7]{MyNiUs14}}]
\label{thm-ushakov}
For every hyperbolic group $G$ there exists a polynomial $p(x)$ such that the following holds.
Suppose that a knapsack expression $E = u^{-1} u_1^* u_2^*\cdots u_{k}^*$ over $G$ has a solution.
Then $E$ has a solution $(n_1, n_2, \ldots, n_k) \in \mathbb{N}^k$ such that $n_i \leq p(|E|)$ for all $i$ satisfying $1 \leq i \leq k$. \qed
\end{theorem}

Let us now consider the \emph{compressed knapsack problem} for $G$.
It is defined in the same way as the knapsack problem, except that the words $u_i \in \Sigma^*$ are given by straight-line programs.
Note that the compressed knapsack problem for $\mathbb{Z}$ is $\NP$-complete~\cite[Proposition 4.1.1]{Haa11}.
Hence, for every group with an element of infinite order, the compressed knapsack problem is $\NP$--hard.
This makes it interesting to look for groups where the compressed knapsack problem is $\NP$--complete.

From Corollary~\ref{coro-CWP-hyperbolic} and Theorem~\ref{thm-ushakov} we prove Theorem~\ref{thm-knapsack-hyp},
which states that compressed knapsack for an infinite hyperbolic group $G$ is $\NP$--complete.

\begin{proof}[Proof of Theorem~\ref{thm-knapsack-hyp}]
Consider a knapsack expression $E = u^{-1} u_1^* u_2^* \cdots u_{k}^*$ over $G$, where $u$ and the $u_i$ are given by straight-line programs ${\mathcal{G}}$ and ${\mathcal{G}}_i$.
We then have $|u_i| \leq 3^{|{\mathcal{G}}_i|/3}$ by Lemma~\ref{lem-SLP-upper-bound}.
Let $N = |{\mathcal{G}}| + \sum_{i = 1}^k |{\mathcal{G}}_i|$ be the input length.

By Theorem~\ref{thm-ushakov}, there exists a polynomial $p(x)$ such that $E$ has a solution if and only if it has a solution $(n_1, n_2 \ldots, n_k) \in \mathbb{N}^k$ with $n_i \leq p(|E|)$ for all $i$ so that $1 \leq i \leq k$.
Thus we obtain a bound of the form $2^{O(N)}$ on the exponents $n_i$.
Hence, we can guess a tuple $(n_1, n_2, \ldots, n_k) \in \mathbb{N}^k$ with all $n_i$ bounded by $2^{O(N)}$ and then check whether it is a solution for $E$.
The latter can be done in polynomial time by constructing from the straight-line programs ${\mathcal{G}}$ and ${\mathcal{G}}_i$ a straight-line program ${\mathcal{H}}$ for $u^{-1} u_1^{n_1} u_2^{n_2} \cdots u_{k}^{n_{k}}$ using Proposition~\ref{prop-power}.
Finally, we check in polynomial time whether $\mathsf{eval}({\mathcal{H}}) =_G 1$ using Corollary~\ref{coro-CWP-hyperbolic}.

The $\NP$--hardness of the compressed knapsack problem for $G$ (an infinite hyperbolic group) now follows from the fact that $G$ has elements of infinite order~\cite[page~156]{GhysdelaHarpe90} and the above mentioned result for $\mathbb{Z}$~\cite[Proposition 4.1.1]{Haa11}.
\end{proof}

\bibliographystyle{hyperplain}

redpajama_set_name: RedPajamaArXiv