\section{Introduction}\label{intro}

\subsection{Our main results}
One useful property to know about a 3-manifold is whether or not it is hyperbolic---that is, whether or not it is homeomorphic to a finite volume quotient of $\mathbb{H}^3$ by a group of isometries acting properly discontinuously.
The decision problem of {\sc hyperbolicity} is computable (\cite{Kuperberg14,Manning02}), but not much is known about its complexity class.
We will focus on the class of cusped orientable 3-manifolds.
Here a \emph{cusped} 3-manifold is a compact orientable 3-manifold with nonempty boundary consisting of a finite disjoint union of tori.
More specifically, we seek to understand the complexity of certifying a negative answer to this decision problem.
The main result of this paper is as follows:

\begin{thm}\label{thm:main}
  If {\sc $S^3$ recognition} lies in \MakeLowercase{co}NP, then among cusped 3-manifolds, {\sc hyperbolicity} lies in \MakeLowercase{co}NP.
\end{thm}

We have taken care to minimize our result's dependence on a \MakeLowercase{co}NP\ solution to {\sc $S^3$ recognition}, the decision problem to recognize $S^3$ among triangulations of manifolds.
Of course, this problem is known to be decidable (\cite{rubinstein1995algorithm,thompson1994thin}) and lie in NP\ (\cite{Ivanov08, Schleimer11}), but the hypothesis is about certificates for affirming a negative result.
If we restrict to the set of irreducible manifolds, we may obtain the unconditional result:

\begin{thm}
  Among irreducible orientable cusped 3-manifolds, {\sc hyperbolicity} lies in \MakeLowercase{co}NP.
\end{thm}

Along the way, we prove the following theorem and thus recover unconditionally the following corollary of Baldwin and Sivek, removing its dependence upon the Generalized Riemann Hypothesis.
We say the {\sc irreducible toroidal recognition} problem is the decision problem to decide if an irreducible manifold is toroidal.

\begin{thm}\label{main_thm_toroidal}
  {\sc Irreducible toroidal recognition} lies in NP.

  In other words, if $\mathcal{T}$ triangulates an orientable closed or cusped 3-manifold that is also irreducible and toroidal, then there is a certificate that $\mathcal{T}$ is irreducible and toroidal that is verifiable in time polynomial in $|\mathcal{T}|$.
\end{thm}

Given the above theorem, the special case of deciding if a knot has a toroidal complement follows directly from the construction of a triangulation (see \cite[\S 7]{HLP99} for the bounded time complexity of this step).
To be precise, we follow the convention that {\sc satellite knot recognition} is the decision problem which takes as its input a knot (here a set of $n$ edges in embedded in $S^3$) and determines if it has a toroidal complement.

\begin{cor}\label{cor_satellite}
  {\sc Satellite knot recognition} lies in NP.
\end{cor}

We structure our certificate according a celebrated theorem of Thurston.
Assuming $M$ is both irreducible and neither a solid torus nor $\mathbb{T}^2 \times I$, Thurston \cite{Thurston82} showed that $M$ is either Seifert fibered, toroidal, or hyperbolic.
Typically, the theorem below is presented according to that trichotomy, but the following reformulation is more useful for disproving hyperbolicity.

\begin{thm}[Thurston \cite{Thurston82}]\label{thm:thurston}
  Let $M$ be a cusped 3-manifold.
  $M$ is non-hyperbolic if and only if it admits an essential connected compact surface of nonnegative Euler characteristic.
\end{thm}

There are but seven connected compact surfaces of nonnegative Euler characteristic: the projective plane $P^2$, the sphere $S^2$, the disk $D^2$, the Klein bottle $K^2$, the torus $T^2$, the M\"{o}bius strip\ $M^2$, and finally the annulus $A^2$.
Thus, to prove our main theorem, it will suffice to give, for any triangulation $\mathcal{T}$ of a non-hyperbolic cusped 3-manifold, a certificate verifiable in time polynomial in $\mathcal{T}$ (that is, polynomial in its number of tetrahedra) that $\mathcal{T}$ admits such a surface.
The certificates we give are either normal such surfaces or appeals to the works of others, which themselves appeal in no small part to normal surfaces.
Thus we will begin the body of this paper with a review of normal surfaces, and of useful intermediate results from \cite{AHT06} and \cite{Lackenby16}.
Then, after building up the necessary intermediate certificates, we give the certificates advertised above.
Before doing so, however, we now give a brief review of the literature.

\subsection{Brief review of some relevant literature}
Haken's foundational result that {\sc unknot recognition} is decidable \cite{Haken} helped establish the importance of algorithms in low dimensional topology using normal surface theory.
Hass, Lagarias and Pippenger \cite{HLP99} analyzed complexity of this problem and showed that {\sc unknot recognition} lies in NP.
Their paper contains a number of other foundational results---namely, the bounds on the size of fundamental and vertex normal surfaces' coordinates---which continue to be relied upon or imitated (for example, later in this paper).

We point the reader to \cite{JT95} for many of the original solutions to important decision problems utilizing normal surface theory, and we also point the reader to Matveev's book \cite{Matveev07} for further background.

In Theorem 3 of \cite{Ivanov08}, Ivanov showed, among many other things, that {\sc $\mathbb{S}^1 \times D^2$ recognition} lies in NP.
We appeal to this result frequently.
This is distinct from {\sc unknot recognition}, since in the latter problem one is allowed the assumption that the given 3-manifold is known to be irreducible.
One could also show that {\sc $\mathbb{S}^1 \times D^2$ recognition} lies in NP\ more or less directly using Schleimer's result in \cite{Schleimer11} that {\sc $S^3$ recognition} lies in NP, after appealing to \cite{AHT06} as Lackenby did to take exteriors in polynomial time.

Reducibility is where we assume that {\sc $S^3$ Recognition} lies in \MakeLowercase{co}NP.
By the work of Zentner in \cite{Zentner16}, this assumption follows from the Generalized Riemann Hypothesis, using his own work on splicing irreducible representations into $SL(2, \mathbb{C})$ and using Kuperberg's work in \cite{Kuperberg14} on turning such representations into nonabelian representations into $SL(2,\mathbb{F}_p)$ for sufficiently small $p$; one bounds the size required on such a prime $p$ using the Generalized Riemann Hypothesis.

Lackenby in \cite{Lackenby16} has shown that among irreducible cusped 3-manifolds, {\sc $\mathbb{S}^1 \times D^2$ recognition} lies in coNP.
In fact, much more is true---he showed that {\sc irreducible knotted recognition} lies in NP.
That is, if $M$ is irreducible and not $\mathbb{S}^1 \times D^2$, then there is a certificate verifying \emph{both} of these properties simultaneously.

For their satellite knot certificate, in \cite{BaldwinSivek17} Baldwin and Sivek made an appeal to the work of Berge \cite{Berge91} and Gabai \cite{Gabai89, Gabai90} on classifying knots in solid tori.
However, Baldwin and Sivek got a certificate using representations into $SL(2, \mathbb{C})$.
Thus, their certificate's size bound depends on Kuperberg's work, and hence on the Generalized Riemann Hypothesis.
Our appeals to normal surface theory removes this dependence in a number of relevant cases.
Nevertheless, we still depend on Berge and Gabai.

\subsection{Acknowledgements}
The second author would like to thank Gary Miller for asking questions about $S^3$ recognition on a car ride from the Pittsburgh airport to city which led to this project.
Both authors would like to thank Bus Jaco and Ben Burton for providing separate, helpful summaries of crushing techniques.
We also wish to thank William Petterssen for a number of helpful conversations while this project was being developed and we are very grateful to the MATRIX Institute who hosted these conversations.
The second author was partially supported by grant from the Simons Foundation (\#524123 to Neil R. Hoffman).

\section{Background}

To provide the minimal background needed in complexity theory, the reader should consult Schleimer's brief summary in \cite{Schleimer11}.
For our purposes, a decision problem \emph{lies in NP} if there is a polynomial time verifiable certificate, or proof, of an affirmative answer.
Likewise, a decision problem \emph{lies in \MakeLowercase{co}NP} if there is a polynomial time verifiable certificate of an negative answer.

We will work throughout in the PL category, and we will use the standard kind of triangulation, defined as follows:

\begin{dfn}
  Given a disjoint union $\overline{\mathcal{T}}$ of closed tetrahedra; and given a partition $\Pi$ of some subset of the faces of these tetrahedra into pairs; and, finally, for each pair $(f,f')$ in $\Pi$, given a cell-isomorphism or \emph{gluing} $\phi_{(f,f')}$ between $f$ and $f'$, one may construct a \emph{triangulation} by identifying the tetrahedra along the gluings, and remembering all this information.
  All triangulations are constructed this way.
  The \emph{underlying space} of a triangulation is the topological space resulting from the identification.

  A triangulation $\mathcal{T}$ with finitely many tetrahedra is a \emph{(material) triangulation} of a compact 3-manifold $M$ when $\mathcal{T}$ is homeomorphic to $M$.
\end{dfn}

Because $\mathcal{T}$ is a representative of the manifold $M$ and is indeed the input to our algorithms, we will use $\mathcal{T}$ to denote the manifold of interest throughout the paper.

Another notion of triangulation is \emph{ideal triangulations}, which typically use fewer tetrahedra.
As useful as ideal triangulations are in other contexts, we eschew them here.
We mention material triangulations only to emphasize this.
It is worth pointing out that, given an ideal triangulation $\mathcal{T}$ of a 3-manifold $M$, one may associate a material triangulation $\mathcal{T}'$ to $M$ in time polynomial in $\mathcal{T}$ by taking a second barycentric subdivision and removing the tetrahedra around the ideal vertices of $\mathcal{T}$.
It is also worth pointing out that the converse is not known to be true in general, given a sufficiently restrictive definition of ``ideal,'' i.e.\,\,disallowing vertices not representing boundary components.

Lackenby prefers to use handle structures instead of triangulations (for good reason; see \cite[\S 1.3]{Lackenby16}), but we only need triangulations in this work.
These two structures are well-known to be polynomially-equivalent; that is, given a handle structure $H$ on a 3-manifold of a given size $h$, one may calculate in time polynomial in $h$ a triangulation $T$ of the same 3-manifold, and vice versa.
Lackenby gives one such equivalence in \cite{Lackenby16}.
One could give a more efficient such method using splitting surfaces as in \cite[Chapter 4]{BurtonPhD}, but we do not pursue this here.

Naturally, our work depends on the theory of normal surfaces; we fix terminology below.

\begin{dfn}
  Suppose $\mathcal{T}$ is an orientable triangulation.
  (All the following definitions depend upon this choice of $\mathcal{T}$.)

  A \emph{normal isotopy} of a triangulation is an isotopy of $\mathcal{T}$ through isomorphisms.

  A \emph{normal disk} in a tetrahedron $\tau$ of $\mathcal{T}$ is a properly embedded disk in $\tau$ normally isotopic to the intersection of $\tau$ with an affine plane transverse to $\tau$.
  If it separates one vertex from the others, or \emph{links} the vertex, then the disk is a triangle.
  Otherwise the plane separates two pairs of vertices, and the disk is a quadrilateral, or \emph{quad}.

  A \emph{normal surface in $\mathcal{T}$} is a properly embedded surface $\Sigma \hookrightarrow \mathcal{T}$ transverse to $\mathcal{T}^{(2)}$ such that $\Sigma$ is the union of finitely many normal disks.

  A \emph{link} of a vertex $v$ of $\mathcal{T}$ is a normal surface in $\mathcal{T}$ consisting of one of each normal triangle linking $v$ in some tetrahedron.
  (These are ``trivial'' normal surfaces.)

  The \emph{normal disk set of $\mathcal{T}$} is the set $\Delta$ of normal isotopy classes of normal disks in $\mathcal{T}$.
  It has cardinality $7\cdot |\mathcal{T}|$.

  The \emph{(normal) coordinates} of a normal surface $\Sigma$ are constituted by the function $x_{\Sigma}: \Delta \to \mathbb{N}$ defined by letting $x_{\Sigma}(d)$ be the number of normal disks of $\Sigma$ in the normal isotopy class $d$.
\end{dfn}

A normal surface is determined up to normal isotopy by its coordinates; therefore, one may combinatorially represent a normal surface via its coordinates.

Not every surface in $\mathcal{T}$ is isotopic to a normal surface.
However, those surfaces most important for 3-manifold topology can usually be so isotoped.
As $\mathcal{T}$ is the input to all of our algorithms, we will refer to a manifold $M$ with triangulation $\mathcal{T}$ simply as $\mathcal{T}$.
We will also regard those properties $\mathcal{T}$ (or $M$) that can be computed from $\mathcal{T}$ in polynomial time as inherent to $\mathcal{T}$.
For example, if $\mathcal{T}$ can be distinguished from $\mathbb{T}^2 \times I$ by a polynomial-time computable invariant such as number of cusps or homology, we say it can be distinguished via the empty certificate.
Our convention here would be to avoid unnecessary storage of certificates in such cases.

\begin{dfn}
  Suppose $\mathcal{T}$ triangulates a compact 3-manifold.
  Suppose $\Sigma$ is a tame, connected, properly embedded surface in $\mathcal{T}$.

  $\Sigma$ is an \emph{essential sphere} when it is an sphere that does not bound a ball.

  $\mathcal{T}$ is \emph{irreducible} when it admits no essential sphere.

  $\Sigma$ is a \emph{compressing disk} when it is a disk whose boundary is essential in $\partial \mathcal{T}$.

  $\mathcal{T}$ is \emph{$\partial$-irreducible} when it is irreducible and it admits no compressing disk.

  $\Sigma$ is \emph{compressible} when there is an essential curve $\gamma$ in $\Sigma$ and a tame embedded disk $D$ in $\mathcal{T}$ such that $D\cap \Sigma = \gamma = \partial D$.

  $\Sigma$ is \emph{$\partial$-compressible} when there is an essential arc $\alpha$ in $\Sigma$ and a tame embedded disk $D$ in $\mathcal{T}$ and an arc $\beta$ of $D$ such that $\alpha = D \cap \Sigma$, $\beta = D \cap \partial \mathcal{T}$, $\alpha \cap \beta = \partial \alpha = \partial \beta$, and $\alpha \cup \beta = \partial D$.

  $\Sigma$ is \emph{$\partial$-parallel}
  when it is isotopic relative to its boundary to a subsurface of $\partial \mathcal{T}$.

  $\Sigma$ is \emph{essential} (assuming it is not a sphere) when it is incompressible, $\partial$-incompressible, and not $\partial$-parallel.

  $\mathcal{T}$ is \emph{toroidal} when it is irreducible and $\partial$-irreducible and admits an essential torus.
\end{dfn}

We refer the reader to \cite{JR03} for a simple ``shrinking'' normalization procedure that produces normal such surfaces from non-normal ones.

Now, we have the following summary which is collection of classical results.
We point the reader to \cite{Matveev07} (see also \cite{JT95}) as it provides a self-contained set of proofs of these results and is framed in a way most convenient for our subsequent arguments.
This proposition is of fundamental importance to this paper, and is how we structure our certificate of non-hyperbolicity and its verification.

\begin{prop}\label{prp:fundFaults}
  There is a finite set $\mathcal{F}$ of normal surfaces computable from $\mathcal{T}$, such that the following is true:
  \begin{itemize}
  \item if there is an embedded $P^2$, then there is one in $\mathcal{F}$; \item otherwise, if there is an essential $S^2$, then there is one in $\mathcal{F}$; \item otherwise, if there is a compressing $D^2$, then there is one in $\mathcal{F}$; \item otherwise, if there is an essential $K^2$, then there is one in $\mathcal{F}$; \item otherwise, if there is an essential $T^2$, then there is one in $\mathcal{F}$; \item otherwise, if there is an essential $M^2$, then there is one in $\mathcal{F}$; \item otherwise, if there is an essential $A^2$, then there is one in $\mathcal{F}$.
  \end{itemize}
\end{prop}

\begin{proof}
  Suppose $\mathcal{T}$ is an orientable triangulation.
  Let $\mathcal{F}$ be the set of fundamental normal surfaces.

  \begin{description}

  \item[$P^2$] If $\mathcal{T}$ admits an embedded $P^2$, then by \cite[Theorem 4.1.12]{Matveev07}, $\mathcal{T}$ admits a fundamental such surface.

  \item[$S^2$] Otherwise, if $\mathcal{T}$ admits an essential sphere, then again by \cite[Theorem 4.1.12]{Matveev07}, $\mathcal{T}$ admits a fundamental such sphere, since $\mathcal{T}$ admits no embedded $P^2$.

  \item[$D^2$] Otherwise, if $\mathcal{T}$ admits a compressing disk, then by the proof of \cite[Theorem 4.1.13]{Matveev07}, $\mathcal{T}$ admits a fundamental such disk, since $\mathcal{T}$ is irreducible.

  \item[$K^2$] Otherwise, if $\mathcal{T}$ admits an essential $K^2$, then by irreducibility there is a normal surface $\Sigma$ isotopic to this Klein bottle, e.g.\,\,by applying the shrinking procedure of \cite{JR03}.
    Suppose $\Sigma = S + S'$.
    We follow an argument similar to the proof of \cite[Lemma 6.4.7]{Matveev07}.
    Since $\mathcal{T}$ is irreducible and orientable, and since $\Sigma$ is incompressible, by \cite[Lemma 3.3.30]{Matveev07} and \cite[Theorem 4.1.36]{Matveev07}, both $S$ and $S'$ are connected, incompressible, and not $S^2$ or $P^2$.
    Hence they both have Euler characteristic 0.
    Also, they are closed.
    Since $\Sigma$ is not orientable, at least one of $S,S'$ is not orientable.
    Without loss of generality, $S$ is not orientable; since it is closed and $\chi(S) = 0$, $S$ is a Klein bottle.
    If $S'$ is not empty, then the weight $w(S) = |S \cap \mathcal{T}^{(1)}|$ is less than $w(\Sigma) = |\Sigma\cap\mathcal{T}^{(1)}|$.
    Hence by descent on weight, one arrives at an embedded Klein bottle $\Sigma$ such that if $\Sigma = S + S'$, then one of $S$ or $S'$ is empty---that is, we arrive at a fundamental normal essential Klein bottle.

  \item[$T^2$] Otherwise, suppose $\mathcal{T}$ admits an essential $T^2$.
    By \cite[Lemma 6.4.7]{Matveev07}, $\mathcal{T}$ admits either a fundamental normal such surface, or a fundamental normal Klein bottle $K$ with $K + K$ being an essential $T^2$.
    But this latter case would mean $K$ was an essential Klein bottle, contrary to assumption.
    Thus $\mathcal{T}$ admits a fundamental normal essential $T^2$.

  \item[$M^2$] Otherwise, if $\mathcal{T}$ admits an essential M\"{o}bius strip\ $M^2$, then it admits a normal essential band $\Sigma$, again by \cite{JR03}.
    Just as before, if $\Sigma = F + F'$, then by the same lemmata, $F$ and $F'$ are connected, incompressible, $\partial$-incompressible, and not $S^2$, $P^2$, or $D^2$.
    Hence their Euler characteristics are 0.
    One of them, say $F$, has exactly one boundary component, and the other $F'$ is closed.
    If $F'$ were nonorientable, then it would be an embedded Klein bottle, contrary to assumption.
    Hence $F$ is nonorientable, and is thus an embedded M\"{o}bius band; and by the same lemmata as above is essential, being incompressible and $\partial$-incompressible.
    By descent as above, $\mathcal{T}$ admits a fundamental normal embedded M\"{o}bius band.

  \item[$A^2$] Otherwise, if $\mathcal{T}$ admits an essential annulus, then it admits a normal such annulus $\Sigma$.
    By \cite[Lemma 6.4.8]{Matveev07}, there is a fundamental such annulus, since $\mathcal{T}$ admits no M\"{o}bius band.
  \end{description}
\end{proof}

Another result of critical importance to this work is the following bound of Hass, Lagarias, and Pippenger.
They get a better bound for vertex normal surfaces (not to be confused with vertex links), but for simplicity's sake we only use fundamental surfaces.

\begin{lem}[Hass, Lagarias, Pippenger {\cite[{Lemma 6.1(2)}]{HLP99}}]\label{lem:hlp}
  If $\mathcal{T}$ is a triangulation of a compact 3-manifold with $t$ tetrahedra, and $\mathcal{F}$ is the set of fundamental normal surfaces of $\mathcal{T}$, then for every $f \in \mathcal{F} \subset \mathbb{N}^{7\cdot t}$,
  \[ \max_{0\leq i < 7\cdot t} f_i \leq t\cdot 2^{7\cdot t + 2}. \]
\end{lem}

The point about this bound is that the surfaces from the previous proposition admit representations of (bit-)size polynomial in $t$, since to represent a surface one may represent its coordinates, and these coordinates one may represent in place-value notation, which only requires space proportional to the logarithm of these coordinates.

The fact that one may represent such a normal surface with a polynomial amount of data suggests, together with Kneser-Haken finiteness, that the topological classification of a normal surface $F$ of total weight $W$ ought to be at least representable with an amount of data polynomial in $\mathcal{T}$ and $\log W$.
In fact, much more is true; we have the following remarkable corollary of Agol, Hass and Thurston in \cite[Corollary 17]{AHT06}, another result to which we appeal frequently:

\begin{prop}[Agol, Hass, Thurston]\label{prp:aht}
  Suppose $\mathcal{T}$ is a triangulation with $t$ tetrahedra, and suppose $F$ is a normal surface in $\mathcal{T}$ of total weight $W = |F \cap \mathcal{T}^{(1)}|$.

  There is an algorithm that, in time polynomial in $\mathcal{T}$ and $\log W$, determines the coordinate vectors of the normal isotopy types of components of $F$, determines the homeomorphism class of each such type, and determines how many of each such type there are.
\end{prop}

Finally, we recall here a crucial intermediate result, \cite[Theorem 9.3]{Lackenby16}, from Lackenby's work regarding knot genus certification, which Baldwin and Sivek also relied upon in \cite{BaldwinSivek17}.

\begin{thm}[Lackenby]\label{thm:lackenby}
  There is an algorithm that takes, as its input,
  \begin{enumerate}
  \item[(i)] a triangulation $\mathcal{T}$, with $t$ tetrahedra, for a compact orientable manifold $M$; and
  \item[(ii)] a vector $\vec{S}$ for an orientable normal surface $S$ with no two components normally isotopic,
  \end{enumerate}
  and provides, as its output, the following data, in time that is bounded by a polynomial in $t \cdot \log |S \cap \mathcal{T}^{(1)}|$.

  If $M'$ is the manifold that results from decomposing along $S$, and $S'$ is the two copies of $S$ in $\partial M'$, and $\mathcal{B}$ is the parallelity bundle for the pair $(M',S')$ with its induced handle structure, then the algorithm determines the following information: a handle structure for $cl(M' - \mathcal{B})$ and, for each component $B$ of $\mathcal{B}$,
  \begin{enumerate}
  \item[(i)] the genus and number of boundary components of its base surface;
  \item[(ii)] whether $B$ is a product or twisted $I$-bundle; and
  \item[(iii)] the location of $\partial_v B$ in $cl(M'-\mathcal{B})$.
  \end{enumerate}

\end{thm}

We have added here the caveat ``with no two components normally isotopic,'' in place of ``for every component $B$ of $\mathcal{B}$'' in \cite[Theorem 9.2]{Lackenby16}, lest the reader worry that the algorithm performs an enumeration over the normal surface's components.
It does no such thing; indeed, consider the surface $2^n \cdot L$ where $L$ is a vertex link.
This has ``polynomial size but exponentially many components''; an algorithm that enumerated over these components would run in as much time.
Algorithms, like Lackenby's, that are based on the Agol-Hass-Thurston machinery work with normal surfaces only via their coordinates, in the same way the Euclidean algorithm works with numbers only via place-value notation.
Running the Euclidean algorithm on, say, the $n$th and $(n+1)$st Fibonacci numbers, would take an amount of time exponential in $n$ if you used \emph{unary notation} (i.e.\,\,tally notation).
Enumerating over \emph{components} of normal surfaces would be a similar mistake.

The reader will note that this algorithm returns a handle structure instead of a triangulation.
As mentioned above, these are polynomially equivalent structures, so we may conclude the following as a corollary.

\begin{prop}\label{prp:exterior}
  There is an algorithm that takes as its input both a compact orientable connected triangulation $\mathcal{T}$ of $t$ tetrahedra and a connected normal surface $S$ in $\mathcal{T}$ given as a vector, and provides as its output a triangulation of the complement in $M$ of a regular neighborhood of $S$, and that moreover provides this output in time polynomial in $t$, $\log |S \cap \mathcal{T}^{(1)}|$, and $|\chi(S)|$.
\end{prop}

This is a slight twist on \cite[Theorem 11.4]{Lackenby16}; we include a proof below for the sake of clarity.
This proof is self-contained, except that we will rely on the notion of \emph{parallelity bundle} from \cite{Lackenby16} without defining it here.

\begin{proof}
  Let $\mathcal{B}$ be the parallelity bundle for the handle structure on $M' = cl(\mathcal{T} \setminus S)$ inherited from $\mathcal{T}$.

  Now, $\partial_v \mathcal{B}$ is a subcomplex of the handle structure on $cl(M' \setminus \mathcal{B})$, for it is identified with such a subcomplex by running the algorithm of Theorem \ref{thm:lackenby}.
  This subcomplex has polynomially many cells.
  Thus $\mathcal{B}$ has polynomially many components that meet $cl(M' \setminus \mathcal{B})$.
  But if $K$ is a component of $\mathcal{B}$ that doesn't meet $cl(M' \setminus \mathcal{B})$, then $K$ is a mapping cylinder from a component of $S$ to a one-sided surface $S'$ that it double-covers, since $S$ is connected.
  Thus $K$ is a regular neighborhood of $S'$.
  There can be only one such component in the exterior of $S$.
  Therefore, $\mathcal{B}$ has polynomially many components.

  For every component $K$ of $\mathcal{B}$, $K$ is an $I$-bundle over a connected compact surface $\Sigma_K$.
  This $I$-bundle structure manifests $K$ as the mapping cylinder of a double cover $p:\Sigma'_K \to \Sigma_K$, where $\Sigma'_K$ is a subsurface of $S$.
  Since $\Sigma_K$ is connected, $\Sigma'_K$ has at most two components.
  Let $Q$ be such a component.
  Then $Q$ is a connected subsurface of $S$.
  Thus we may write $Q = \Theta \setminus D$, where $\Theta$ is an essential subsurface of $S$ (i.e. a subsurface every boundary component of which is essential in $S$), and $D$ is a union of disks with disjoint closures in $\Theta$.
  Since $\Theta$ is an essential subsurface of $S$, $\chi(\Theta) \geq \chi(S)$.
  Hence $\chi(Q) = \chi(\Theta) - |D| \geq \chi(S) - |D|$.
  Now, every disk in $D$ corresponds to some subcomplex of $\partial_v \mathcal{B}$; any two disks either correspond to the same subcomplex or to subcomplexes with disjoint 2-cells; and at most two disks correspond to any given subcomplex.
  Thus, letting $C$ be the number of 2-cells in $\partial_v \mathcal{B}$, we have $|D| \leq 2\cdot C$.
  Hence $\chi(Q) \geq \chi(S) - 2\cdot C$.
  Since $\Sigma_K'$ has at most two components, $\chi(\Sigma_K') \geq 2 \cdot \chi(S) - 4\cdot C$.
  Since $\Sigma_K'$ double covers $\Sigma_K$, $\chi(\Sigma_K) \geq \chi(S) - 2\cdot C$.
  Since $K$ is an $I$-bundle over $\Sigma_K$, $K$ admits a handle structure polynomial in $|\chi(\Sigma_K)|$; in fact, it admits a handle structure polynomial in $|\chi(\Sigma_K)|$ and in $C$ with appropriate vertical boundary isomorphic to $\partial_v\mathcal{B}$.
  Moreover, given the necessary structure on $\partial_v\mathcal{B}$ and given the homeomorphism type of $\Sigma_K$ and the $I$-bundle type, one may construct this handle structure in time polynomial in $|\chi(\Sigma_K)|$ and $C$.
  Since $|\chi(\Sigma_K)|$ admits the upper bound $|\chi(S)| + 2\cdot C$ linear in $\chi(S)$ and $C$, one may construct the desired handle structure on $K$ in time polynomial in $\chi(S)$ and $C$; since $C$ is polynomially bounded in $t$ and $\log |S\cap\mathcal{T}^{(1)}|$, we may construct such a handle structure on $K$ in time polynomial in $\chi(S)$, $t$, and $\log |S\cap\mathcal{T}^{(1)}|$.
  Since there are but polynomially many components $K$ of $\mathcal{B}$, we can construct a handle structure $\mathcal{B}'$ on $\mathcal{B}$ and an isomorphism between $\partial_v \mathcal{B}'$ and $\partial_v \mathcal{B}$ in time polynomial in $\chi(S)$, $t$, and $\log |S\cap\mathcal{T}^{(1)}|$.
  Identifying $\mathcal{B}'$ to the handle structure constructed on $cl(M'\setminus \mathcal{B})$ by the algorithm of \ref{thm:lackenby}, in the manner determined by the same algorithm, one thereby constructs a handle structure on $M'$ in time polynomial in $\chi(S)$, $t$, and $\log |S\cap\mathcal{T}^{(1)}|$.
  From that handle structure, one may then, as alluded to above, construct a triangulation on $M'$ in polynomial time.
\end{proof}

\section{Certificates}

\subsection{Three-sphere certificates}
Rubinstein and Thompson both describe algorithms for 3-sphere recognition \cite{rubinstein1995algorithm,thompson1994thin}.
Later, it was shown that such algorithms could also produce an appropriately sized certificate affirming a manifold is indeed $S^3$.

\begin{thm}[Ivanov \cite{Ivanov08}, Schleimer \cite{Schleimer11}]\label{thm:s3np}
  {\sc $S^3$ recognition} lies in NP.
\end{thm}

The companion question remains open.

\begin{conj}\label{conj:s3conp}
  {\sc $S^3$ recognition} lies in \MakeLowercase{co}NP.
\end{conj}

Zentner \cite[Theorem 11.2]{Zentner16}
proved the following, providing strong evidence for the conjecture.

\begin{thm}[Zentner]
  {\sc $S^3$ recognition} lies in \MakeLowercase{co}NP, provided that the Generalized Riemann Hypothesis holds.
\end{thm}

\subsection{Isomorphism signatures}\label{subsec:isosigs}

It may happen on occasion that we will want our triangulations to have a particular form---for instance, we may want to have a triangulation that induces a one-vertex triangulation on a boundary component.
One may simplify a triangulation to have such properties in polynomial time, and then one may generate certificates for the simplified triangulation.
However, these are not certificates for the original triangulation.

To promote these certificates to certificates of the original triangulation, it suffices to give a polynomial-sized certificate that the simplified triangulation triangulates the same underlying manifold as does the old triangulation.
It is almost obvious that one may do this for polynomial-length sequences of Pachner moves, layerings, close-the-book moves, and other ``atomic'' modifications of triangulations.
However, it is not clear how to name such a sequence in a way that is invariant under isomorphism of the triangulation.
Moreover, a representation of, say, a normal surface in a triangulation as a vector of numbers requires some choice of ordering on the normal disk-types in that triangulation.
One can consistently specify a natural such ordering given an ordering of the tetrahedra of the triangulation, and given, for each tetrahedron, an ordering of its vertices.
But then to use that vector as a certificate, one must make sure to make that particular collection of choices of ordering for one's triangulation.

Therefore, following \cite[\S 3]{Schleimer11}, let us say that a triangulation together with such choices is a \emph{labelled triangulation}.
Let two such structures be \emph{equivalent} when there is an isomorphism between the triangulations preserving the orderings (or \emph{labellings}).
In \cite{Burton11} Burton has constructed a injective \emph{signature} function from the set of equivalence classes of labelled triangulations to the set of bit-sequences; and has constructed a function, the \emph{isomorphism signature} function, from the class of labelled triangulations to the set of bit-sequences, whose level classes are in bijection with \emph{combinatorial isomorphism classes of triangulations}; and, most importantly for us, these functions may be computed in polynomial time in their inputs.
This gives canonical ways of putting coordinates on normal surfaces and other such objects in triangulations.

Therefore, throughout the work below, we assume that every triangulation is labelled, and in fact has the labelling whose signature is its isomorphism signature, which is just the lexicographic minimum of the set of signatures over all its possible labellings---we assume it has its \emph{canonical labelling}.
When implementing the algorithms below, the first thing one should do with a newly constructed triangulation or with an input triangulation is to endow it with its canonical labelling.

\subsection{Simplifying triangulations}\label{subsec:simpl}

A standard ``close-the-book-and-layer'' algorithm (e.g.\,\,the algorithm in \cite{SnapPy}, \texttt{close\textunderscore cusps.c}) returns, in time polynomial in $\mathcal{T}$, a new triangulation $\mathcal{T}'$ such that $\mathcal{T}'$ has at most three more tetrahedra than $\mathcal{T}$ and such that $\mathcal{T}'$ induces one-vertex triangulations on $\partial \mathcal{T}'$; and also returns a proof $P$ of size polynomial in $\mathcal{T}$ that $\mathcal{T}$ and $\mathcal{T}'$ are homeomorphic.
The proof is, as described above, a sequence of triples $(\sigma,i,b)$, where $\sigma$ is an isomorphism signature, $i$ is a number indicating a boundary edge, and $b$ is a bit indicating whether to fold along that boundary edge or layer along it.
This allows one to promote, as above, a polynomial-sized certificate of a property of $\mathcal{T}'$ to a polynomial-sized certificate of a property of $\mathcal{T}$.

As simple as the above algorithm is, it has this disadvantage, that it increases the number of tetrahedra.
If the given triangulation is assumed to be irreducible and $\partial$-irreducible, then one can do much better via crushing to a 0-efficient triangulation.
The following are essentially restatements and summaries of results from \cite{JR03}.

\begin{lem}\label{lem:0FVTX}
  Suppose $\mathcal{T}$ is a compact material triangulation that is not 0-efficient.
  Then $\mathcal{T}$ admits a vertex normal surface $\Sigma$ that is either an embedded $P^2$, a non-vertex-linking $S^2$, or a non-vertex-linking $D^2$.
\end{lem}

\begin{proof}
  Suppose $\mathcal{T}$ is a compact material triangulation that is not 0-efficient.
  Then $\mathcal{T}$ admits a connected non-vertex-linking normal surface $\Sigma$ with $\chi(\Sigma) > 0$.
  Suppose $n\cdot \Sigma = X + Y$ for nonempty normal surfaces $X,Y \neq 0$.
  Then $n\cdot \chi(\Sigma) = \chi(X) + \chi(Y) > 0$.
  Hence either $\chi(X) > 0$ or $\chi(Y) > 0$.
  Thus some component $k$ of $X$ or $Y$ has $\chi(k) > 0$.
  Now, since $\Sigma$ is connected and non-vertex-linking, no component of $X$ or $Y$ is a vertex link.
  Hence in particular, $k$ is not a vertex link.
  However, since $X$ and $Y$ are nonempty, $|k \cap \mathcal{T}^{(1)}| < |\Sigma \cap \mathcal{T}^{(1)}|$.
  Thus by descent on $|\Sigma \cap \mathcal{T}^{(1)}|$ (the \emph{weight} of $\Sigma$), $\mathcal{T}$ admits a connected non-vertex-linking vertex-normal surface $\Sigma$ with $\chi(\Sigma) > 0$.
  The lemma follows.
\end{proof}

The existence of the 0-efficient triangulation in the next proposition can be established by \cite[Proposition 5.9, Theorem 5.17]{JR03}; the certificate is essentially due to Schleimer (see \cite[Theorem 16.1]{Schleimer11}).

\begin{prop}\label{prp:0Fcert}
  Suppose $\mathcal{T}$ is a triangulation of a compact, orientable, $P^2$-irreducible, $\partial$-irreducible 3-manifold with no $S^2$ boundary component.

  Then there is a 0-efficient triangulation $\mathcal{T}'$ of the same 3-manifold, and also there is a certificate that $\mathcal{T} \cong \mathcal{T}'$ of size polynomial in $\mathcal{T}$.
\end{prop}

Note carefully that we do not claim there is a polynomial-size certificate that the 0-efficient triangulation $\mathcal{T}'$ is in fact 0-efficient---we only provide a certificate that $\mathcal{T} \cong \mathcal{T}'$.

\begin{proof}
  Suppose $\mathcal{T}$ is a triangulation of a compact, orientable, $P^2$-irreducible, $\partial$-irreducible 3-manifold.

  Suppose $\mathcal{T}$ is 0-efficient.
  Then define $cert_{0F}(\mathcal{T}) = ((\mathcal{T}, \emptyset), Nil)$.

  Suppose instead that $\mathcal{T}$ is not 0-efficient.
  Then by Lemma \ref{lem:0FVTX}, there is a vertex-normal non-vertex-linking surface $\Sigma$ in $\mathcal{T}$ with $\chi(\Sigma) > 0$.
  Since $\mathcal{T}$ is $P^2$-irreducible, $\Sigma$ is not an embedded projective plane.
  Therefore, $\Sigma$ is a sphere or disk cutting off one 3-ball from $\mathcal{T}$.
  Crush $\mathcal{T}$ along $\Sigma$ to get $\mathcal{T}_\Sigma$.
  Let $\mathcal{T}'$ be the component of $\mathcal{T}_\Sigma$ not homeomorphic to a ball---there is such a component since $\mathcal{T}$ is not a 3-ball, having no sphere boundary component.
  Then by \cite{JR03}, $\mathcal{T}'$ is homeomorphic to $\mathcal{T}$, since $\mathcal{T}$ has no $RP^3$ or $L(3,1)$ summands, being irreducible.
  Define $cert_{0F}(\mathcal{T}) = ((\mathcal{T}, \Sigma), cert_{0F}(\mathcal{T}'))$.

  Note that a call to $cert_{0F}$ will make at most $|\mathcal{T}|-1$ recursive calls, since every crushing strictly decreases the number of tetrahedra, since it crushes along a non-vertex-linking surface.

  The function $cert_{0F}$ returns a list of pairs $(T,S)$, where each $T$ is a triangulation with $|T| \leq |\mathcal{T}|$, and where each $S$ is a vertex-normal surface in $T$.
  Since $S$ is vertex-normal, the size of $S$ (log of the weight) is bounded by a polynomial in $T$.
  Hence the size of $(T,S)$ is bounded by a polynomial in $T$, and hence by a polynomial $P$ in $\mathcal{T}$.
  Hence the size of the list $cert_{0F}(\mathcal{T})$ is bounded by $|\mathcal{T}|\cdot P(|\mathcal{T}|)$, and so has size polynomial in $\mathcal{T}$.

  Suppose $L$ is a putative list of crushings.
  If $L$ is empty, $verify(L) = fail$.
  If instead $L$ has an element $(T,S)$, determine whether or not $S = \emptyset$ is equivalent to $tail(L) = Nil$.
  If not, then $verify(L) = fail$.
  Otherwise, if $S = \emptyset$ and $tail(L) = Nil$, $verify(L) = success$.
  And finally, if $S \neq \emptyset$ and $tail(L) \neq Nil$, then let $(T',S') = head(tail(L))$.
  Now determine whether or not $T$ crushes to $T'$ along $S$.
  If not, $verify(L) = fail$.
  Otherwise, $verify(L) = verify(tail(L))$.
\end{proof}

\subsection{Closed essential surface certificates}

To certify a manifold is toroidal, we need to give a certificate that a torus or Klein bottle is essential.
In an earlier version of this paper, we gave such certificates.
After we posted this version, Marc Lackenby kindly pointed out that Theorem 1.6 in the latest revision of \cite{Lackenby16} can be used to prove the following result, which we had conjectured in our earlier version.

\begin{thm}[Lackenby]\label{thm:handlebody}
  {\sc Handlebody recognition} is in \MakeLowercase{co}NP\ among irreducible 3-manifolds, and {\sc Handlebody recognition} is in \MakeLowercase{co}NP\ modulo GRH.
\end{thm}

We then found that it is straightforward to use this theorem and Lackenby's new results to prove the following theorem and corollary.
(We thank Nathan Dunfield for a conversation in which he brought the problem of $I$-bundle recognition to our attention.)

\begin{thm}\label{thm:ibundle}
  For every compact surface $\Sigma$, {\sc $\Sigma\times I$ recognition} and {\sc $\Sigma\,\tilde{\times}\,I$ recognition} are in NP\ among orientable 3-manifolds, and are in \MakeLowercase{co}NP\ among irreducible orientable 3-manifolds.
\end{thm}

\begin{cor}\label{cor:ess_surf}
  {\sc Closed essential surface recognition} is in NP\ $\cap$ \MakeLowercase{co}NP\ for normal surfaces $\Sigma$ in connected, orientable, irreducible, $\partial$-irreducible 3-manifolds.
\end{cor}

Note carefully that in Theorem \ref{thm:ibundle} the size of the certificate returned by the algorithm is polynomial in the input triangulation and in $|\chi(\Sigma)|$, whereas in Corollary \ref{cor:ess_surf} the size is polynomial in the input triangulation and in the size of the given normal surface $\Sigma$, i.e.~in $\log|\Sigma \cap \mathcal{T}^{(1)}|$.

The reader should also note that the NP\ portion of Theorem \ref{thm:ibundle} follows almost immediately from the normal-almost-normal sweepout certificates in section 6 of Schleimer's 2001 PhD thesis \cite{SchleimerPhD}.
Moreover, it is relatively easy to show from Theorem 3 of \cite{Ivanov08} that one can extend the $\mathbb{T}^2 \times I$ recognition algorithm of \cite{Haraway14} to show that {\sc $\mathbb{T}^2 \times I$ recognition} is in NP.
We regard these approaches as more viable for implementation with current software libraries like Regina (see \cite{Regina}).
However, the result also follows directly from Lackenby's work, so for ease of reference we rely on \cite{Lackenby16}.

We turn to the proofs of these results now.

\begin{proof}[Proof of Theorem \ref{thm:handlebody}]
  Let $\mathcal{T}$ be a triangulation with boundary $F$ a genus $g$ surface.
  Suppose $\mathcal{T}$ is not a handlebody of genus $g$.

  If $H_1(\mathcal{T},\mathbb{Z}) \not\cong \mathbb{Z}^g$, then $\mathcal{T}$ is not a handlebody.
  Since homology is computable in polynomial time, $\mathcal{T}$ may be verified not to be a handlebody in polynomial time, with no certificate necessary.

  Otherwise, we start out assuming $\mathcal{T}$ is irreducible and will address the reducible case afterward.

  In the irreducible case, find a maximal set $\hat{D}$ of pairwise-normally-non-isotopic normal disks in $\mathcal{T}$.
  By \cite[Theorem 6.2]{JT95}, we may arrange that the disks of $\hat{D}$ have coordinate vectors that all are vertices of the same facet of the convex polytope defined by the matching equations (see \cite[Theorem 6.2]{JT95}).
  By \cite{HLP99} and Haken finiteness, the union of these disks has polynomial bit-size.
  Using Lackenby's method for taking complements (Theorem \ref{thm:lackenby} above), construct on the exterior $\mathcal{T} - \hat{D}$ a triangulation $\hat{\mathcal{T}}$ of size polynomial in $|\mathcal{T}|$.

  Suppose every component of $\hat{\mathcal{T}}$ had $\beta_1 = 0$.
  Then each component would have a sphere boundary component.
  By irreducibility, each component would be a ball, and $\mathcal{T}$ would be a handlebody, contrary to assumption.
  So some component $K$ of $\hat{\mathcal{T}}$ has $\beta_1 > 0$, and is irreducible.
  If $\partial K$ were compressible, then it would admit a compressing disk.
  This would imply that $\mathcal{T}$ would admit yet another normal disk disjoint from $\hat{D}$ and not normally isotopic to any element of $\hat{D}$, contrary to the maximality of $\hat{D}$.
  Thus $\partial K$ is incompressible.
  We may construct a certificate $c_{inc}$ of this fact of size polynomial in $|\mathcal{T}|$ by \cite[Theorem 1.7]{Lackenby16}.
  Together, we contend $\hat{D}$, $\hat{\mathcal{T}}$, $K$, and $c_{inc}$ constitute a certificate that $\mathcal{T}$ is not a handlebody.

  Finally, if $\mathcal{T}$ is reducible, then we run the standard argument of constructing a polynomially sized reduction along a reducing sphere using Lackenby's method (Theorem \ref{thm:lackenby} above) and applying \cite[Theorem 11.2]{Zentner16}, which depends upon GRH.

  To verify an empty certificate, just determine whether or not $\mathcal{T}$ is a homology handlebody.
  If not, the certificate is verified; otherwise, the verification fails.
  To verify the certificate constructed when $\mathcal{T}$ is an irreducible homology handlebody, verify that $\mathcal{T}$ surgers along $\hat{D}$ into $\hat{\mathcal{T}}$; then verify that $K$ is a component of $\hat{\mathcal{T}}$; then verify that $c_{inc}$ is a certificate that $\partial K$ is incompressible.
  All these verifications may be performed in time polynomial in the sizes of the certificates.
  By \cite{AHT06} we may verify as well that $\hat{D}$ is a disjoint union of discs.
  Thus we may verify that $K$ is gotten from $\mathcal{T}$ by surgering along discs.
  But we have also verified that $K$ has incompressible boundary.
  Furthermore, we may calculate $\beta_1(K)$; if it is 0, the verification fails.
  Otherwise, $\beta_1(K) > 0$.
  There is no handlebody with $\beta_1 > 0$ and with incompressible boundary.
  Hence $K$ is not a handlebody.
  However, surgering a handlebody along a disc always produces another handlebody (or two).
  Hence $\mathcal{T}$ cannot be a handlebody.
  Thus the given certificate demonstrates $\mathcal{T}$ is not a handlebody.

  Finally, to verify the reducibility certificate, verify that the given surface is a sphere, that the reduction along that sphere is as given in the certificate, and that the reduction is nontrivial using the verification of \cite[Theorem 11.2]{Zentner16}.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:ibundle}]
  Suppose $\Sigma$ is a compact surface.

  First, suppose $\mathcal{T}$ triangulates a manifold of the form $\Sigma \times I$, with $\Sigma$ orientable.
  If $\Sigma$ has nonempty boundary, then $\mathcal{T}$ is a handlebody with the same Euler characteristic as $\Sigma$.
  Theorem 3 of \cite{Ivanov08} provides a certificate $h_\mathcal{T}$ that $\mathcal{T}$ is a handlebody.
  To verify that $\mathcal{T}$ triangulates $\Sigma\times I$, verify with $h_\mathcal{T}$ that $\mathcal{T}$ is a handlebody, then check, in polynomial time, that $\mathcal{T}$ has the same Euler characteristic as $\Sigma$.
  On the other hand, if $\Sigma$ is closed, then $(\mathcal{T},\emptyset)$ is a product sutured manifold.
  Let $\mathcal{H}$ be the handle structure dual to $\mathcal{T}$, i.e.~the handle structure gotten from thickening the dual spine of $\mathcal{T}$.
  One may construct this handle structure in time polynomial in $|\mathcal{T}|$.
  Then $\mathcal{H}$ is of uniform type, as required in Theorem 12.1 of \cite{Lackenby16}, since its 0-handles' intersection patterns with the 1- and 2-handles are subtetrahedral (in fact, tetrahedral, being the duals of the tetrahedra of the triangulation).
  So Theorem 12.1 of \cite{Lackenby16} applies, and $(\mathcal{H}, \emptyset)$ admits a polynomial-time verifiable certificate $ps_\mathcal{T}$ that it is a product sutured manifold.
  To verify that $\mathcal{T}$ triangulates $\Sigma\times I$, verify with $ps_\mathcal{T}$ that it is a product sutured manifold, then check, in polynomial time, that its two boundary components are homeomorphic to $\Sigma$.

  Second, suppose that $\mathcal{T}$ triangulates a twisted $I$-bundle $\Sigma\tilde{\times}I$ with $\Sigma$ nonorientable.
  Again, if $\Sigma$ has nonempty boundary, one may verify the product as before using Ivanov's handlebody certificate.
  If instead $\Sigma$ is closed, then $\mathcal{T}$ admits a double cover $\tilde{\mathcal{T}}\cong \tilde{\Sigma}\times I$ that is a product $I$-bundle over the orientation cover of $\Sigma$.
  One may certify that $\tilde{\mathcal{T}}$ is $\tilde{\Sigma}\times I$, and this constitutes a proof that $\mathcal{T}$ is $\Sigma\tilde{\times}I$.
  Thus, {\sc $\Sigma\times I$ recognition} and {\sc $\Sigma\times I$ recognition} are in NP\ among orientable 3-manifolds.

  Now we show that they are in \MakeLowercase{co}NP\ among orientable irreducible 3-manifolds.
  This problem is solved in Theorem \ref{thm:handlebody} when $\Sigma$ has nonempty boundary, so assume $\Sigma$ is closed.
  Suppose $\mathcal{T}$ is irreducible and orientable and is not $\Sigma\times I$.
  If $\mathcal{T}$ is distinguishable from $\Sigma \times I$ in homology, we need no certificate.
  Otherwise, $\mathcal{T}$ is homologically equivalent to $\Sigma \times I$.
  Let $i^\ast: H^1(\partial\mathcal{T},\mathbb{Z}) \to H^1(\mathcal{T},\mathbb{Z})$ be induced from the inclusion map.
  Then $\ker i^\ast$ is isomorphic to the first cohomology of each of the boundary surfaces.
  We may calculate a basis $B$ for $\ker i^\ast$ in polynomial time.
  We contend that some element of $B$ has positive Thurston norm.
  For a contradiction, suppose that the Thurston norm is 0 on $B$.
  Then for every $b \in B$, there is a tame annulus $A(b)$ in $\mathcal{T}$ bounding $b$.
  We may isotope the annuli so that they are transverse.
  By a standard argument, after isotoping the annuli to lie in minimal position, they only intersect in core curves or essential arcs.
  If two distinct annuli intersected in core curves, then resolving their intersection shows that the annuli's boundaries were homologous, contrary to distinctness.
  Hence after isotoping the annuli to lie in minimal position, they intersect only in essential arcs.
  Now, the union of their boundary curves on $\partial \mathcal{T}$ is filling; its complement consists of discs.
  Let $X$ be a regular neighborhood of the union of $\partial \mathcal{T}$ with these annuli.
  The boundary of $X$ consists of $\partial \mathcal{T}$ and spheres.
  By irreducibility the spheres must bound balls, and they must bound them away from $\partial \mathcal{T}$.
  Hence $\mathcal{T}$ is $\Sigma \times I$, contrary to assumption.
  Therefore, in fact there must be some $b \in B$ with positive Thurston norm.
  We may certify it has positive Thurston norm via \cite[Theorem 1.5]{Lackenby16}.
  Verifying that $b$ has positive Thurston norm proves that $\mathcal{T}$ is not $\Sigma\times I$, for all elements of the kernel of the inclusion map for $\Sigma \times I$ bound annuli.
  Finally, if $\Sigma$ is nonorientable, we may verify that $\mathcal{T}$ is not $\Sigma\tilde{\times} I$ by showing either that $\mathcal{T}$ does not admit a double cover, or by showing that its unique connected double cover is not $\Sigma\times I$.
\end{proof}

\begin{proof}[Proof of Corollary \ref{cor:ess_surf}]
  Suppose $\Sigma$ is a closed essential normal surface in $\mathcal{T}$ with $\mathcal{T}$ orientable, irreducible, and $\partial$-irreducible.
  That is, suppose $\Sigma$ is incompressible and not boundary parallel.
  ($\Sigma$ is automatically $\partial$-incompressible, being closed, and this is why we restrict to the closed case.)
  If $\Sigma$ is nonorientable, its normal double is its orientation cover, and is essential if and only if $\Sigma$ is.
  Thus we may assume $\Sigma$ is orientable.
  To certify $\Sigma$ is incompressible, take a polynomial-time verifiable triangulation $\mathcal{T}'$ of its exterior with Theorem \ref{thm:lackenby}, and use \cite[Theorem 1.7]{Lackenby16} to verify that $\mathcal{T}'$ has incompressible boundary.
  To show $\Sigma$ is not boundary-parallel, either show that $\mathcal{T}'$ is connected, or for both components of $\mathcal{T}'$ use Theorem \ref{thm:ibundle} to verify that they are not $\Sigma \times I$.
  The latter certificate will be verifiable in time polynomial in $\mathcal{T}'$ and $\Sigma$, which by Theorem \ref{thm:lackenby} is polynomial in $\mathcal{T}$ and $\Sigma$.
\end{proof}

\subsection{Toroidality}
We now consider the other decision problems discussed in the introduction.
We begin with Theorem \ref{main_thm_toroidal}, on toroidality.
First we require the following proposition.

\begin{prop}\label{prp:tornp}
  {\sc Toroidal recognition} lies in NP\ among compact, connected, irreducible, $\partial$-irreducible, orientable 3-manifolds admitting no essential Klein bottles.
\end{prop}

\begin{proof}
  Suppose $\mathcal{T}$ is a triangulation of a compact, connected, irreducible, $\partial$-irreducible, orientable 3-manifold that is toroidal.
  By Proposition \ref{prp:fundFaults}, there is a fundamental essential torus $F$ in $\mathcal{T}$.
  By Lemma \ref{lem:hlp}, $F$ is representable in size polynomial in $\mathcal{T}$.
  By Proposition \ref{prp:exterior}, we may construct a triangulation $\mathcal{T}'$ of the exterior of $F$ in time polynomial in the sizes of $\mathcal{T}$ and $F$, hence in time polynomial in $\mathcal{T}$.
  If $\mathcal{T}'$ is connected, then we return $F$ as our certificate.
  Otherwise, since $F$ is essential and $\mathcal{T}$ is connected, $\mathcal{T}'$ has two components, $L$ and $R$, neither of which is homeomorphic to $\mathbb{T}^2 \times I$, neither of which is homeomorphic to $\mathbb{S}^1 \times D^2$, and both of which are irreducible.
  The certificate we return is the quintuple $(F, L_T, R_T, L_D, R_D)$, where $L_T,R_T$ are the certificates guaranteed by Theorem \ref{thm:ibundle} that $L$ and $R$ are not $\mathbb{T}^2 \times I$, and where $L_D,R_D$ are the certificates guaranteed by \cite[Theorems 1.6 and 1.8]{Lackenby16} that $L,R$ are irreducible and are not solid tori.

  Suppose $c$ is a putative toroidality certificate.
  Then either $c = F$ or $c = (F,L_T,R_T,L_D,R_D)$ for some normal surface $F$.
  By Proposition \ref{prp:aht}, we may determine in time polynomial in $\mathcal{T}$ and $F$ whether or not $F$ is a normal torus.
  If it is not, then the verification fails.
  Otherwise, by Proposition \ref{prp:exterior}, construct a triangulation $\mathcal{T}'$ of the exterior of $F$ in $\mathcal{T}$, in time polynomial in $\mathcal{T}$ and $F$.
  Determine whether or not $\mathcal{T}'$ is connected; we may do so in time polynomial in $\mathcal{T}'$, and hence in $\mathcal{T}$.
  If it is connected, then $c$ is verified if and only if it is not a tuple.
  If $\mathcal{T}'$ is not connected, and $c$ is a single surface, then the verification fails.
  Otherwise, $c$ is a tuple as above.
  Then since $\mathcal{T}$ is connected and $F$ is connected, $\mathcal{T}'$ has two components $L$ and $R$, which we may determine in time polynomial in $\mathcal{T}'$, and hence in $\mathcal{T}$.
  Then $c$ is verified if and only if $L_T,R_T$ are verified as proofs that $L,R$ are not $\mathbb{T}^2 \times I$ and $L_D,R_D$ are verified as proofs that $L,R$ are irreducible and not solid tori.
  By Theorem \ref{thm:ibundle} and \cite[Theorems 1.6 and 1.8]{Lackenby16}, these verifications take time polynomial in $\mathcal{T}'$ (and hence polynomial in $\mathcal{T}$), $F$, $L_T$, $R_T$, $L_D$, and $R_D$.
\end{proof}

We may now prove a theorem asserted in the introduction.

\begin{proof}[Proof of Theorem \ref{main_thm_toroidal}]
  Suppose $\mathcal{T}$ is a triangulation of a connected, orientable, irreducible, $\partial$-irreducible, toroidal 3-manifold.
  Either $\mathcal{T}$ contains an essential Klein bottle or not.
  If it does, then by Corollary \ref{cor:ess_surf}, there is a certificate of this fact verifiable in time polynomial in $\mathcal{T}$.
  If it does not, then since $\mathcal{T}$ is toroidal, by Proposition \ref{prp:tornp} there is a certificate verifiable in time polynomial in $\mathcal{T}$ that $\mathcal{T}$ contains an essential torus.
  In the latter case we already have a proof of toroidality.
  In the former case, the double of the Klein bottle is a torus, and since the Klein bottle is essential, the torus is necessarily essential.
\end{proof}

Corollary \ref{cor_satellite} follows immediately; it only requires going from a knot diagram to a triangulation, which is a standard argument of Hass, Lagarias, and Pippenger \cite[Lemma 7.1]{HLP99}.
This result was achieved by Baldwin and Sivek in \cite{BaldwinSivek17} under the additional assumption of the Generalized Riemann Hypothesis.

\subsection{Essential M\"{o}bius strip s and annuli}\label{sec:annuli}

We now discuss the final situations: when the manifold contains an essential M\"{o}bius strip\ or annulus.

\begin{prop}\label{prp:m2np}
  Suppose $\mathcal{T}$ is a compact orientable $P^2$-irreducible, $\partial$-irreducible triangulation.
  If $\mathcal{T}$ admits a properly embedded M\"{o}bius strip, then there is a certificate of this fact verifiable in time polynomial in $\mathcal{T}$.
\end{prop}

\begin{proof}
  Suppose $\mathcal{T}$ admits an embedded M\"{o}bius strip\ $M$.

  If $M$ is compressible, then $\mathcal{T}$ admits an embedded $P^2$, contrary to $P^2$-irreducibility.
  If $M$ is incompressible but is $\partial$-compressible, let $D$ be a $\partial$-compressing disk for $M$.
  Then surgering $M$ along $D$ yields another disk $Z$.
  Since $M$ is incompressible, $Z$ is a compressing disk for $\partial \mathcal{T}$, contrary to $\partial$-irreducibility.
  Thus $M$ must be incompressible and $\partial$-incompressible.
  Therefore $M$ is not $\partial$-parallel, and hence $M$ is essential.
  By Proposition \ref{prp:fundFaults} there is a fundamental normal embedded M\"{o}bius strip\ $\mu$ in $\mathcal{T}$.
  By Lemma \ref{lem:hlp} and Proposition \ref{prp:aht}, $\mu$ constitutes a certificate verifiable in time polynomial in $\mathcal{T}$ that $\mathcal{T}$ admits an embedded M\"{o}bius strip.
\end{proof}

The following is the main result of this subsection.

\begin{prop}\label{prp:annulusxNP}
  Suppose $\mathcal{T}$ is compact and orientable.

  Suppose further that $\mathcal{T}$ has no essential surfaces of nonnegative Euler characteristic apart from annuli.

  If $\mathcal{T}$ admits an essential embedded annulus, there is a certificate of this fact verifiable in time polynomial in $\mathcal{T}$.
\end{prop}

We prove this at the conclusion of this subsection, using the following three results.

\begin{lem}\label{lem:nonsepAs}
  Suppose an irreducible $\partial$-irreducible triangulation $\mathcal{T}$ admits a non-separating annulus $A$.
  Then $A$ is essential.
\end{lem}

\begin{proof}
  Inessential annuli are separating in irreducible, $\partial$-irreducible 3-manifolds.
\end{proof}

We now show that if a non-separating annulus exists in the manifold, there is one of manageable size for our purposes.

\begin{lem}\label{lem:nonsepAx}
  Suppose $\mathcal{T}$ is compact and orientable.
  Suppose further that $\mathcal{T}$ has no essential surfaces of nonnegative Euler characteristic apart from annuli.
  Finally, suppose $\mathcal{T}$ admits a non-separating annulus.

  Then $\mathcal{T}$ admits a fundamental non-separating annulus.
\end{lem}

\begin{proof}
  Suppose $A$ is a non-separating annulus in $\mathcal{T}$.
  Then $A$ admits a normal representative, being essential by Lemma \ref{lem:nonsepAs}.
  Suppose $A = \sum_{s \in X} s$ for some collection $X$ of connected normal surfaces.
  By Proposition \ref{prp:0Fcert} we may assume $\mathcal{T}$ is 0-efficient.
  Since $A$ is connected and has no vertex link components, neither is any element of $X$ vertex linking.
  Thus for all $s \in X$, $\chi(s) \leq 0$.
  But since $\chi(A) = 0$, this necessitates that for all $s \in X$, $\chi(s) = 0$.
  Now since $A$ has boundary, some element $\alpha \in X$ has boundary.
  If $\alpha$ had but one boundary component, then $\alpha$ would be an embedded M\"{o}bius strip.
  Since $\mathcal{T}$ has no embedded $P^2$, $\partial \alpha$ is essential, and since $\mathcal{T}$ is $\partial$-irreducible, $\alpha$ is essential---but then $\mathcal{T}$ has an essential M\"{o}bius strip, contrary to assumption.
  Hence $\alpha$ cannot have a single boundary component.
  Thus $\alpha$ must have two boundary components, and be itself an annulus.
  Since $\alpha$ has the same boundary components as $A$, $\alpha$ too is $\pi_1$-injective, as is $A$.
  Since these lie on different boundary components of $\mathcal{T}$, in fact $\alpha$ is not $\partial$-compressible; hence $\alpha$ is also a non-separating, essential annulus.
  Thus, by descent on weight, $\mathcal{T}$ admits a fundamental essential non-separating annulus.
\end{proof}

The following proposition handles one of the final cases we need to deal with, an essential separating annulus.

\begin{prop}\label{prp:SxDx2}
  Suppose $\mathcal{T}$ is an irreducible, $\partial$-irreducible 3-manifold obtained by identifying two solid tori along two disjoint annuli in their boundaries, and has one boundary component, a torus.
  Let $A$ be the annulus in $\mathcal{T}$ gotten by identifying these annuli.

  Then $\mathcal{T}$ is Seifert fibered over the disk with two exceptional fibers, and $A$ is an essential annulus fibered by regular fibers.
\end{prop}

\begin{proof}
  Call the annuli of the solid tori $\alpha$ and $\beta$.

  Suppose first that $\alpha$ and $\beta$ are $\pi_1$-injective in their respective components.
  Then the $\SxD$ components admit Seifert fiberings such that $\alpha$ and $\beta$ are fibered by regular fibers.
  If either $\alpha$ or $\beta$ is longitudinal in its component, then $\mathcal{T}$ would be $\SxD$, and hence be $\partial$-reducible, contrary to assumption.
  Therefore, neither $\alpha$ nor $\beta$ is longitudinal.
  Thus, both the Seifert fiberings have exceptional fibers.
  Therefore, $\mathcal{T}$ is Seifert fibered over a disk with two exceptional fibers, and $A$ is an essential annulus fibered by regular fibers.

  Thus to conclude the proof it will suffice to assume not both $\alpha$ and $\beta$ are $\pi_1$-injective in their components, and derive a contradiction.
  As before, if but one of them were $\pi_1$-injective, then $\mathcal{T}$ would have a compressible boundary component, contrary to $\partial$-irreducibility.
  Thus, suppose both $\alpha$ and $\beta$ are not $\pi_1$-injective in their respective components.
  If either were meridional, then $\mathcal{T}$ would admit a non-separating sphere, contrary to irreducibility.
  Thus we may assume both $\alpha$ and $\beta$ are trivial.
  But in this case, $\mathcal{T}$ would have two boundary components.
\end{proof}

We may now conclude this subsection with a proof of its main result.

\begin{proof}[Proof of Prop.\,\ref{prp:annulusxNP}.]
  Suppose $\mathcal{T}$ has no essential surfaces of nonnegative Euler characteristic, except that it has an essential annulus.
  By \cite[Theorems 1.6 and 1.7]{Lackenby16} there is a certificate $c_I$ that $\mathcal{T}$ is a compact irreducible $\partial$-irreducible 3-manifold verifiable in time polynomial in $\mathcal{T}$.
  Now, since $\mathcal{T}$ admits an essential annulus, but has no essential surfaces of nonnegative Euler characteristic apart from this annulus, it is Seifert-fibered.
  Since it is geometrically atoroidal by assumption, it is Seifert-fibered either over a disk with two exceptional fibers, an annulus with at most one exceptional fiber, or over a pair of pants.

  In the latter two cases, $\mathcal{T}$ has at least two boundary components, and therefore admits a non-separating annulus.
  Hence by Lemma \ref{lem:nonsepAx}, $\mathcal{T}$ admits a fundamental such annulus $A$.
  By Proposition \ref{prp:exterior}, one may construct a triangulation $\mathcal{T}'$ of $\mathcal{T} - A$ from $A$ and $\mathcal{T}$ in time polynomial in $\mathcal{T}$ and $\log |A\cap \mathcal{T}^{(1)}|$.
  By Proposition \ref{prp:exterior} and Lemma \ref{lem:nonsepAs}, since $\mathcal{T}'$ is connected, $c_I$ constitutes a certificate that $A$ is essential.
  Thus, $(A, c_I)$ together constitute a certificate that $\mathcal{T}$ admits an essential annulus.
  Since $A$ and $c_I$ have size polynomial in $\mathcal{T}$, this certificate has size polynomial in $\mathcal{T}$.

  In the first case, $\mathcal{T}$ has one boundary component, and all essential annuli are separating.
  If $\mathcal{T}$ admits a horizontal essential annulus, then $\mathcal{T}$ is either $\mathbb{T}^2 \times I$ or $K^2\tilde{\times}I$; since $\mathcal{T}$ has but one boundary component, $\mathcal{T}$ must be $K^2\tilde{\times}I$.
  But we assumed $\mathcal{T}$ admitted no Klein bottle, a contradiction.
  Thus $\mathcal{T}$ only admits fibered essential annuli.
  By Proposition \ref{prp:fundFaults} $\mathcal{T}$ admits a fundamental essential annulus $A$, and by the above argument, $A$ is fibered.
  Thus $\mathcal{T} - A$ is two solid tori, and $\mathcal{T}$ fits the conditions of Proposition \ref{prp:SxDx2}.
  Now, by Proposition \ref{prp:exterior} we may triangulate $\mathcal{T} - A$ by $\mathcal{T}'$ given $A$ and $\mathcal{T}$ in time polynomial in $\mathcal{T}$ and $\log |A\cap \mathcal{T}^{(1)}|$, and by \cite[Theorem 3]{Ivanov08}, we may construct a certificate $c_t$ that $\mathcal{T}'$ is two solid tori, verifiable in time polynomial in $\mathcal{T}'$, and hence polynomial in $\mathcal{T}$.
  Thus, $c_I$ and $c_t$ together constitute a proof that $A$ is essential, by Proposition \ref{prp:SxDx2}.
  So $(A, c_I, c_t)$ constitutes a certificate that $\mathcal{T}$ admits an essential annulus.
  Since $A$ and $c_I$ have size polynomial in $\mathcal{T}$, and since $c_t$ has size polynomial in $\mathcal{T}'$, and hence polynomial in $\mathcal{T}$, this certificate has size polynomial in $\mathcal{T}$.
\end{proof}

\subsection{Non-hyperbolicity}
We end this section on certificates with the main theorem stated in the introduction, following the outline of Proposition \ref{prp:fundFaults}.

\begin{proof}[Proof of Thm.\,\ref{thm:main}.]
  Suppose $\mathcal{T}$ is a compact orientable triangulation and $\partial \mathcal{T}$ is a nonempty union of tori, and suppose $\mathcal{T}$ is not hyperbolic.
  Then by Theorem \ref{thm:thurston}, $\mathcal{T}$ admits an essential surface of nonnegative Euler characteristic.

  If $\mathcal{T}$ admits an embedded projective plane, then by Proposition \ref{prp:fundFaults} it admits a fundamental normal such surface $\Sigma$.
  $\Sigma$ itself constitutes a proof against hyperbolicity, verifiable as an embedded projective plane in time polynomial in $\mathcal{T}$ by the bounds of Lemma \ref{lem:hlp} and the algorithm of Proposition \ref{prp:aht}.

  Otherwise, if $\mathcal{T}$ admits an essential sphere, then by Proposition \ref{prp:fundFaults}, since it has no embedded projective plane, it admits a fundamental normal essential sphere $\Sigma$.
  If $\Sigma$ is non-separating, then $\Sigma$ on its own constitutes a proof against hyperbolicity, verifiable in time polynomial in $\mathcal{T}$ by the bounds of Lemma \ref{lem:hlp} the algorithm of Proposition \ref{prp:aht}, and the exterior algorithm of Proposition \ref{prp:exterior}, since one may determine whether or not a triangulation (in this case, the exterior of $\Sigma$) is connected in time polynomial in the triangulation.
  Otherwise, the exterior $\mathcal{T}' = \mathcal{T} - \Sigma$ has two components $L'$ and $R'$; cap them off with balls to get the connect-summands $L$ and $R$ of $\mathcal{T}$.
  By assumption {\sc $S^3$ recognition} is in coNP, so there are certificates $c_L$ and $c_R$ verifiable in time polynomial in $L$ and $R$, and hence in $\mathcal{T}$, that $L$ and $R$ are not $S^3$.
  Thus $(\Sigma, c_L, c_R)$ constitutes a certificate verifiable in time polynomial in $\mathcal{T}$ that $\mathcal{T}$ is reducible, and hence is not hyperbolic.

  Otherwise, if $\mathcal{T}$ admits a compressing disk, then by irreducibility, $\mathcal{T}$ must be a solid torus.
  There is a certificate $c_d$ that $\mathcal{T}$ is a solid torus verifiable in time polynomial in $\mathcal{T}$ by Theorem 3 of \cite{Ivanov08}.

  Otherwise, if $\mathcal{T}$ admits an essential Klein bottle or torus, then by Corollary \ref{cor:ess_surf} there is a certificate $c_{ess}$ of this fact verifiable in time polynomial in $\mathcal{T}$.

  Otherwise, if $\mathcal{T}$ admits an essential M\"{o}bius strip, then by Proposition \ref{prp:m2np} there is a certificate $c_m$ of this fact verifiable in time polynomial in $\mathcal{T}$.

  Otherwise, and finally, if $\mathcal{T}$ admits an essential annulus, then by Proposition \ref{prp:annulusxNP}, there is a certificate $c_a$ of this fact verifiable in time polynomial in $\mathcal{T}$.

  If $\mathcal{T}$ has none of these surfaces, then since $\mathcal{T}$ is Haken, having nonempty torus boundary, by \cite{Thurston82} $\mathcal{T}$ is hyperbolic contrary to assumption.
\end{proof}

\section{Discussion}

One initial remark is that in practice, one would want to use vertex normal surfaces instead of fundamental normal surfaces.
Reproving the above results for vertex normal surfaces would be a useful next task to do.

We point out that much of Zentner's analysis relies on establishing irreducible $SL(2, \mathbb{C})$ representations of toroidal manifolds.
Theorem \ref{main_thm_toroidal} removes the need for splicing, and hence reduces one to the case of closed, irreducible, atoroidal 3-manifolds---that is, by Perelman's resolution to Thurston's Geometrization Conjecture, it reduces one to geometric 3-manifolds.
We can further assume that the manifold is \emph{small}, i.e.~it does not contain an incompressible surface of positive genus.
Otherwise, we can use an incompressible surface which is given by a fundamental normal surface, together with \cite[Theorem 1.7]{Lackenby16} as a certificate of incompressibility, that the manifold is not $S^3$.
Thus, if the following conjecture is true, then {\sc $S^3$ recognition} is in fact in \MakeLowercase{co}NP, and the results of this paper are unconditionally true.

\begin{conj}\label{conj:S3inCoNP}
  If $\mathcal{T}$ triangulates a small geometric integral homology sphere, and $\mathcal{T}$ is not $S^3$, then there is a proof that $\mathcal{T}$ is not $S^3$ of length polynomial in $\mathcal{T}$.
  That is, among small geometric integral homology spheres, {\sc $S^3$ recognition} is \MakeLowercase{co}NP.
\end{conj}

Zentner's \cite[Theorem 11.2]{Zentner16} combines with Kuperberg's work to give a proof of this conjecture, assuming the Generalized Riemann Hypothesis.
To remove this assumption, it seems a promising line of inquiry to approach this first by considering small Seifert spaces, for the hyperbolic integral homology spheres will likely prove much more difficult to verify.

We will conclude with a discussion of the affirmative problem.
As mentioned in the introduction, a 3-manifold $M$ is said to be hyperbolic if $M\cong \mathbb{H}^3/\Gamma$, such that $vol(\mathbb{H}^3/\Gamma) < \infty$ and $\Gamma$ is a subgroup of the isometry group acting properly discontinuously.
Now, an ideal triangulation $\mathcal{T}$ of $M$ admits a \emph{strict angle structure} if it determines a map from $\mathbb{R}^{3n} \to \mathbb{R}^n$ that corresponds each pair of opposite edges in a tetrahedron are assigned a positive number, the dihedral angle, such that all (six) dihedral angles in a tetrahedron sum to $2\pi$ and all all dihedral angles in an edge class of $\mathcal{T}$ sum to $2\pi$.
Thus, an angle structure is a solution to a system of linear equations that lies in the positive cone of the solution space.
Work of Casson and Rivin \cite{rivin1994euclidean}  (see also \cite{futer2011angled}) shows that the existence of such a structure rules out each of the obstructions to non-hyperbolicity, so that a strict angle structure on $\mathcal{T}$ implies the hyperbolicity of $M$.
We point out that if a triangulation supports an angle structure, an argument analogous to Lemma \ref{lem:hlp} shows there is a fundamental solution to the angle structure equations that can be verified in polynomial time.
The relevant question is then ``Which triangulations support angle structures?''
To determine how far an input triangulation $\mathcal{T}$ is from a triangulation that supports an angle structure, we ask the following question:

\begin{question}
  Is there a polynomial $P$ such that for any ideal triangulation $\mathcal{T}$ of a cusped hyperbolic 3-manifold, there is an ideal triangulation $\mathcal{T}'$ supporting a strict angle structure that is connected to $\mathcal{T}$ by at most $P(|\mathcal{T}|)$ 2-3 and 3-2 moves?
\end{question}

An affirmative answer to that question together with an affirmative answer to Conjecture \ref{conj:S3inCoNP} would provide an affirmative answer to the following:

\begin{question}
Is the {\sc Hyperbolicity problem} for cusped manifolds in NP $\cap$ coNP?
\end{question}

\bibliographystyle{plain}


\section{Introduction}
Language Models (LM) are a key component in building Automatic Speech Recognition (ASR) systems. The most common approach to building LMs for ASR systems is to learn back-off n-gram models on large text corpora. Recurrent Neural Language Models (NLM) have been shown to consistently outperform traditional n-gram language models from language modeling benchmarks \cite{bengio2003a, schwenk2007continuous, mikolov2010recurrent, jozefowicz2016exploring}.

It is challenging to incorporate NLMs directly into ASR decoding partly because, unlike n-gram models, they model unlimited context history, resulting in exponential explosion in the decoder search space,
and partly because in a large vocabulary ASR system the number of acoustically plausible hypotheses can be very large. There has been prior work in the area to address this issue \cite{hori2014real} but it is still computationally very expensive. Alternatively, a more common approach is to run the ASR decoding in two passes, where the first-pass ASR system is decoded with an n-gram language model to generate a pruned search space in the form of a word lattice or an n-best hypothesis list. In the second-pass, this pruned word lattice is rescored with a stronger neural language model. One of the drawbacks of using a two-pass strategy for a real-time streaming ASR system is that the computation in the second-pass of rescoring is performed after the completion of the streaming first-pass decoding. Hence, this additional computation in the second-pass manifests itself in the form of pure latency for the ASR system. Moreover, an additional drawback is that the stronger NLM is not used during first-pass decoding, which potentially results in losing good hypotheses due to beam search.

Our main contribution in this paper is to call out and address several challenges in bringing NLMs into a latency sensitive ASR system.  In particular, the challenges that we address are
\begin{itemize}
\item Training the NLM on multiple heterogenous corpora, effectively a domain adaptation problem
\item Incorporating the NLM into the ASR system, while limiting the latency impact. This includes strategies both to reduce the second-pass NLM computation and to get benefit from the NLM in the first-pass of decoding

\item Pesonalizing NLM by passing biases for classes such as contact names from the first-pass model through the NLM
\end{itemize}

The rest of the paper is organized as follows. Section \ref{section:challenges} describes our proposed method to tackle each of challenges that we address in this work. In particular, in Section \ref{section:domain-adaptation}, we describe our solution to the domain adaptation problem, in Section \ref{section:fast-inference} we describe our solution for fast inference including the usage of self-normalized models and quantization. Section \ref{section:generate} describes the usage of synthetic data generated from the NLM, to improve the first-pass model and hence the n-best hypothesis list used in second-pass rescoring.

 In Section \ref{section:special-token-handling}, we talk about how we handle neural rescoring when the first-pass model is a class based n-gram model \cite{brown1992class} with personalized biases. In Section \ref{experimental-setup}, we describe our experimental setup and in Section \ref{section:results-and-discussion}, we dive into our results. We conclude in Section \ref{section:conclusions} and outline directions for future work.

\section{Methods and Challenges Addressed}
	\label{section:challenges}

\subsection{Domain adaptation}
	\label{section:domain-adaptation}

In a practical ASR system, the LM is often trained on multiple heterogenous corpora, comprising a mix of written corpora and manually transcribed spoken text corpora from various domains.
These corpora may differ in terms of their vocabulary, content, style, argots, etc \cite{bellegarda2004statistical}.
We require a solution to train a neural LM on such heterogenous training data. We present two approaches below in Sections \ref{section:data-mixing} and \ref{section:transfer-learning} to deal with this.

\subsubsection{Data mixing}
	\label{section:data-mixing}
Training an n-gram language model on a variety of diverse corpora is straightforward. A typical strategy is to train separate n-gram models on each corpus, and combine them through linear interpolation with weights optimized to minimize perplexity on an in-domain development set \cite{gandhe2018scalable, raju2018contextual}. N-gram models have the benefit that the final linearly interpolated model, is also represented as an n-gram model. This allows for easy integration of the interpolated model into the ASR system. NLMs however, require a different approach to learning from heterogenous corpora, as a linear interpolation of NLMs, results in an ensemble model with much higher computation.

In this paper, we propose a novel solution to this problem which is simple yet effective. Parameters of neural networks are typically estimated using a variant of stochastic gradient descent, and this method relies on each minibatch being an Independent and Identically Distributed (iid) sample of the distribution we are trying to learn. Thus, we construct minibatches stochastically, by drawing samples from each corpus with probability according to its relevance weight. This has an advantage over other alternatives such as scaled loss function because it allows the combination of corpora with arbitrarily different sizes and relevance weights, and in a practical system, both can vary by 2-3 orders of magnitude.
For relevance weights, we construct n-gram models from each data source and optimize their linear interpolation weights on a development set.
While these weights are not necessary optimal we found that they work well in practice.
In the future, we plan to investigate methods for learning the relevance weights as part of NLM training procedure.

\subsubsection{Transfer learning through fine tuning}
	\label{section:transfer-learning}

One of the often used approaches to deal with the domain adaptation problem is to use fine-tuning, i.e., to train a neural network on a large out-of-domain dataset and subsequently fine-tune the parameters of the model on an in-domain dataset. Some of the parameters can optionally be fixed during the adaptation, typically those corresponding to the lower layers of the model which learn more generic transformations that are not domain specific. This has been successfully applied in computer vision \cite{krizhevsky2012imagenet,zeiler2014visualizing} and NLP \cite{mou2016transferable}.
The downside to this approach is that it does not leverage the fact that each individual out-of-domain corpus has varying relevance to the target domain. Moreover, the model also faces the challenge of catastrophic forgetting \cite{mccloskey1989catastrophic, ratcliff1990connectionist}, where the model loses past knowledge of the pre-trained weights. In order to get benefits from this method and alleviate some of its drawbacks, this approach can be combined with the data mixing strategy described in Section \ref{section:data-mixing}. The model is first pre-trained on the out-of-domain data, and the data mixing strategy is used during the fine tuning stage.

\subsection{Fast inference solutions}
	\label{section:fast-inference}

\subsubsection{Self-normalized models}
In NLMs, the probability of word $w_{i}$ given it's word history \textbf{h} is given by Eqn. \ref{eqn:self-normalization} below:

 \begin{equation}
   p(w_{i}|\textbf{h}) = \frac{exp(z_{i})}{\sum_{j=1}^{|V|} exp(z_{j})} = \frac{exp(z_{i})}{Z(\textbf{h})}
   \label{eqn:self-normalization}
 \end{equation}

\noindent
where $z_{i}$ is the unnormalized logit corresponding to word $w_{i}$ which is computed as an inner product,
$z_{i}=exp(\textbf{c}^{T}\textbf{e}_{w_{i}} + b_{i})$ where $\textbf{c}^{T}$ is the hidden output context vector and $\textbf{e}_{w_{i}}$, $b_{i}$ are the output word embedding vector and bias value for word $w_{i}$. The normalization term $Z(\textbf{h}) = \sum_{j=1}^{|V|} exp(z_{j})$ is known as the partition function, and it involves a summation over all words in the vocabulary. In large vocabulary NLMs, most of the computation cost is incurred to compute the partition function that produces a proper distribution over the vocabulary as this cost is proportional to the vocabulary size.

There has been a lot of prior work on reducing this computation cost, during both training time and inference time \cite{mikolov2011extensions,morin2005hierarchical,chen2016efficient,shi2014variance} either by approximating the partition function or by modifying the loss function to encourage the model to learn to produce approximately normalized scores (self-normalization).

The self-normalization approach allows us to compute only the scores for the query words thus eliminating the dependency on the vocabulary size. One of the approaches that can be used to train self-normalized models is to add a regularization term during training which encourages the normalization term of the softmax to be close to one \cite{devlin2014fast,chen2016strategies,andreas2015when}. Alternatively, Noise Contrastive Estimation (NCE) based training results in neural networks with inherent self-normalization properties \cite{mnih2012a,vaswani2013decoding,chen2015recurrent,zoph2016simple}. The self-normalization properties of these two broad strategies are emperically compared in \cite{goldberger2018self}.  While both strategies perform well computation-wise for inference, the NCE method has the benefit that it is faster during training time as well. NCE based training does not require computation of the full softmax at training time resulting in significant training speed-ups, which is independent of the output vocabulary size.  In this work, we use NCE to train the Neural LMs since it has two very desirable properties of speeding up the computation during both training and inference.

\subsubsection{Post-training Quantization}
\label{section:quantization}
Quantization of the weights and activations of trained models to 16-bit fixed-point representation is performed to reduce computational cost during inference time. We perform a per-column quantization of the weight matrices, where different shifts and scales are used for each column. We found that this type of quantization performs better that using a global shift and scale for the entire matrix. This method has similarities to the per-channel quantization for convolutional networks in past work \cite{krishnamoorthi2018quantizing}, which uses a different scale and shift for each convolutional kernel. While other work has explored quantization-aware training to squeeze out lower bit representations without accuracy loss, we leave this to future work.

\subsection{Generating synthetic data for first-pass LM}
\label{section:generate}

There is a major drawback of using an NLM strictly in the second-pass to rescore lattices or n-best lists. A weaker n-gram LM is used in the first-pass and some hypotheses may be pruned, which makes them unrecoverable in the second-pass rescoring. Prior work \cite{hori2014real} has attempted to tackle this problem by incorporating scores from the NLM into the first-pass beam search, however this is computationally expensive.

In our system, we take the approach proposed in \cite{deoras2011variational}, namely we construct an n-gram approximation of NLM by sampling a large text corpus from NLM and estimating an n-gram model from that corpus.
Unlike \cite{deoras2011variational}, however, we use a \emph{subword} NLM to generate synthetic data so that the generated corpus will not be limited to the vocabulary of the current version of the ASR system. Sentences containing out of vocabulary words are discarded.
This way, as the vocabulary changes from version to version, we can re-use the same synthetic data.

\subsection{Handling personalized first-pass LM}
\label{section:special-token-handling}

The first-pass LM may have classes \cite{brown1992class} with personalized biases, for example contact names \cite{aleksic2015improved}.
An NLM trained on general data, however, would not have good estimates for such highly personalized words or phrases.
In such cases, we trust the scores of the personalized first-pass LM more than the scores of a general NLM and we do the following:
Surround class content with tags \verb|<class>| and \verb|</class>|, and the words between the tags will retain their first-pass LM scores but they are still passed through the NLM in order to update its state so that the words after the closing tag will be estimated using the correct history.

\section{Experimental Setup}

\label{experimental-setup}
In all of the experiments in this paper, we build an ASR system that targets the message dictation task. The ASR system comprises first-pass LM trained on a variety of in- and out-of-domain corpora, including written text data and transcribed speech data. The transcribed speech data is from real user-agent interactions, and is bucketed into two separate categories - (1) message dictation specific data and (2) all other types of user-agent interactions. The transcribed messaging data which comprises of approximately 5 million words of text, is our only in-domain data corpus.
The written text corpora contain over 50 billion words in total. One corpus is a 150M word long-form voicemail dataset. Although superficially similar, distributionally it is quite different from our task: for example, the average utterance length in this dataset is 67 words while our in-domain transcribed corpus has only 15 words on average.

A Kneser-Ney (KN) \cite{kneser1995improved} smoothed n-gram language model is estimated from each corpus, and the final first-pass LM is a linear interpolation of these component LMs. The interpolation weights are estimated by minimizing the perplexity on target development set, in this case transcribed message dictation utterances. In experiments that use NLM generated data, we estimate a separate KN smoothed LM on the synthesized data. This n-gram LM is used as an additional component in the linear interpolation.

The NLM used in the second-pass rescoring is trained on the voicemail and message dictation corpus only, leaving out the other larger written text corpora. The reasoning behind this is that, the other corpora have a relatively low weight in the n-gram linear interpolation, and they are not that crucial to our message dictation task. The linear interpolation weights from the KN smoothed n-gram LM are 0.78 and 0.22 respectively for the message transcription and the voicemail task. In experiments which use data mixing to train the NLM, these weights are used as relavance scales for the corresponding corpora.

The NLM architecture is two LSTMP \cite{hochreiter1997long, sak2014long} layers, each comprising 1024 hidden units projected down to a dimension of 512. In addition, there are residual connections \cite{he2016deep} between the layers. The models are quantized to 16-bit fixed-point representation as described in Section \ref{section:quantization}. The NLM is used to rescore 10-best hypotheses generated from first-pass decoding.

From in-domain corpus, we extract the vocabulary of 60k most frequent words. All NLM models use this vocabulary and out of vocabulary tokens are mapped to \verb|<unk>|.
Note that the first-pass ASR system has a larger vocabulary, 160k, plus new words can be introduced via personalized classes.
In rescoring experiments (but not for perplexity computation), we scale the probability of \verb|<unk>| token by a factor of $10^{-5}$, i.e., we assume a uniform distribution over the "missing" vocabulary.

\section{Results and Discussion}
\label{section:results-and-discussion}

\subsubsection{Domain adaptation experiments}
Table \ref{table:data-mixing} shows perplexity results comparing NLMs trained on a single data source against different domain adaptation methods described in Sections \ref{section:data-mixing} and \ref{section:transfer-learning}: mixing multiple corpora, applying transfer learning (fine-tuning), and combining both methods.
First, we confirm that our voicemail corpus is indeed out-of-domain: perplexity of an NLM model trained on just that data is 116.0, more than double the perplexity of a model trained on in-domain corpus only, 55.8.
Next, we study the impact of the two domain adaptation strategies.
The results from Table \ref{table:data-mixing} show a 12.6\% relative improvement in perplexity using transfer learning compared to a baseline trained on in-domain message dictation data only. The model is trained through fine-tuning i.e. initially learning a model on the out-of-domain voicemail corpus and further fine-tuning on in-domain message dictation data. This is in line with prior work in literature. More interestingly, by training the model directly on data mixed from both messaging and voicemail data with the relevance weights estimated from an interpolated KN smoothed n-gram model, we can obtain a 13.4\% improvement in perplexity compared to the baseline model. These results are very promising, since the models trained with the data mixing approach, provide slightly better perplexity results, and train significantly faster than the transfer learning approach. The disparity in training speeds is because the transfer learning approach requires two rounds of training, with the pre-training round performed on a significantly larger out-of-domain corpus (which is usually the case, since there is far lesser in-domain training data available). In the data-mixing approach, the model converges much quicker, seeing several epochs of the in-domain data and fewer epochs (possibly lesser than one) on the out-of-domain data. This is for the simple reason that the in-domain corpus is much smaller and the sampling weights of the two corpora is typically skewed towards the in-domain corpus (0.78 in our experiments).

Finally, it is possible to combine the two approaches described above, i.e., first pre-training the model on out-of-domain data and then fine-tuning on a mixture of in-domain and out-of-domain data. This results in a 16.1\% relative improvement in perplexity compared to the baseline, which is better than each of the individual approaches alone. In all future experiments, we use the best NLM obtained from both data-mixing and fine-tuning

\begin{table}[th]
  \caption{Perplexity results for domain adaptation. Voicemail corpus is out-of-domain for the message dictation task. "Mix" refers to the data mixing approach}
  \label{table:data-mixing}
  \centering
    \begin{tabular}{l | l | r }

    \toprule
    \multicolumn{1}{c}{\textbf{Pretrain Corpus}} & \multicolumn{1}{c}{\textbf{Train Corpus}} & \multicolumn{1}{c}{\textbf{PPL}} \\
    \midrule
    -  & Voicemail & 116.0 \\
    -  & Messaging & 55.8 \\
    Voicemail & Messaging & 48.8 \\
    - & Voicemail + Messaging mix & 48.3 \\
    Voicemail & Voicemail + Messaging mix &  46.8 \\
    \bottomrule
  \end{tabular}

\end{table}

\subsubsection{Inference speed impact of self-normalized LM}
Table \ref{table:self-normalized-ppl} shows that the perplexity of unnormalized and normalized models are very close, which will allow us to use unnormalized probabilities for the second-pass rescoring saving a bulk of the inference computation time.
In order to show this, we compare the p50 and p90 percentiles for latency added purely due to the second-pass rescoring. This is shown in Table \ref{table:wer-numbers}, where the rescoring latency of the self-normalized NCE LM is lower than the softmax LM by about 700ms at p50 and 3100ms at p90 percentiles.

\begin{table}[th]
  \caption{Perplexity results comparing normalized and unnormalized NCE models on a voicemail development set. Unnormalized probabilities do not include the softmax normalization factor}
  \label{table:self-normalized-ppl}
  \centering
    \begin{tabular}{l | l }
    \toprule
    \multicolumn{1}{c|}{\textbf{Model}} & \multicolumn{1}{c}{\textbf{PPL}} \\
    \midrule
    Softmax NLM  & 19.42  \\
    NCE NLM (normalized) & 19.95  \\
    NCE NLM (unnormalized) & 20.44  \\
    \bottomrule
  \end{tabular}

\end{table}

\subsubsection{WER Impact from NLM}
Table \ref{table:wer-numbers} shows that we are able to obtain 1.6\% relative WER reduction from using NLM-generated synthetic data. Since this is just an update to the first-pass LM there is no increase in latency. These results are in line with the perplexity improvements seen in Table \ref{table:sampling-nlm} with the inclusion of NLM-generated synthetic data. Note that the NLM used to generate the synthetic data is a subword LM, discarding sentences with out of vocabulary words with respect to the first-pass ASR system. In Table \ref{table:sampling-nlm}, the perplexity number of the NLM reported in the last row is of a softmax word-based LM, included as a fair reference for comparison with the KN smoothed n-gram perplexity numbers.
Finally, performing a 10-best second-pass rescoring using self-normalized NLM gets us a net relative WER reduction of 6.2\%. Note that the WER reduction from both, the softmax NLM and self-normalized NCE NLM, are very similar and in line with the perplexity numbers of Table \ref{table:self-normalized-ppl}.

\begin{table}[th]
  \caption{Relative Word Error Rate Reduction (WERR) and rescoring latency numbers, showing the effect of including NLM synthetic data and rescoring with softmax vs. unnormalized NCE NLM}
  \label{table:wer-numbers}
  \centering
  \footnotesize
	\begin{tabular}{l | c | r | r | r}
    \toprule
    \multicolumn{2}{c|}{\textbf{LM}} & \multicolumn{1}{c|}{\textbf{WERR}} &\multicolumn{2}{c}{\textbf{Rescoring latency}} \\
    \textbf{First-pass} & \textbf{Second-pass}  & & P50 & P90 \\
        \midrule
    Baseline & - &  - & - & - \\
    ~+Syn data & - & 1.6\% & -  & - \\
    ~+Syn data & Softmax NLM & 6.3\% & 767ms & 3396ms\\
    ~+Syn data & NCE NLM & 6.2\% & 65ms & 285ms\\
    \bottomrule
  \end{tabular}

\end{table}

\begin{table}[th]
  \caption{Perplexity results comparing n-gram LMs with and without NLM generated synthetic data on a message dictation test set. "Msg" refers to transcribed message dictation data, "Synthetic Msg" refers to data generated from NLM and "Others" refers to all other available corpora}
  \label{table:sampling-nlm}
  \centering
  \footnotesize
	\begin{tabular}{l | l |c}
    \toprule
    \multicolumn{1}{c|}{\textbf{LM}} & \multicolumn{1}{c|}{\textbf{Train data}} &\multicolumn{1}{c}{\textbf{PPL}} \\
    \midrule
    KN-4g & Msg & 63.71 \\
    KN-4g-Interp & Msg + Others & 60.81  \\
    \midrule
    KN-4g-Syn & Synthetic Msg & 58.34 \\
    KN-4g-Interp-Syn & Msg + Synthetic Msg + Others & 58.11 \\
    \midrule
    NLM & Msg & 46.85 \\
    \bottomrule
  \end{tabular}

\end{table}

\subsection{Impact from personalized bias from first-pass LM}
\label{section:results-special-tok}
Recognition of contact names is important for a message dictation application. The ASR system in this paper is specifically focused on message dictation payload, where the recognition of contact names, within the message are important from a user experience perspective. For example, a fairly common message such as "hey john how was your day" requires accurate recognition of the name "john", which is challenging for a rare or out of vocabulary name. This benefits from the usage of a class-based LM, with a single class for contact names, since it allows us to use personalized contact names list for biasing the model towards user specific information.
This is measured through the Entity WER metric. To measure this, we tag each word in our test data using an in-house Named Entity Recognition (NER) tagger. The Entity WER is defined as $(num\_substitutions+num\_deletions)/num\_reference\_words$. The hypothesis and reference are aligned in order to calculate the number of substitutions and deletions corresponding to the tagged reference words. Note that we do not include insertions due to difficulty in attributing whether an insertion error was caused by the entity or the other surrounding words. The results in Table \ref{table:special-tokens} showing the Entity WERR for Person names, demonstrate that by appropriately handling the contacts class in the NLM through class tags, we are able do slightly better than a naive approach of rescoring these with the NLM. These class tags enabled us to induce personalized bias in the rescorer by retaining the first-pass scores for the contact names, ignoring the score from the NLM but using the word input to update the LSTM state information. This method was previously described in detail in Section \ref{section:special-token-handling}. Overall, this enabled accuracy improvements for contact name recognition, which is important to user experience.

\begin{table}[th]
  \caption{Relative Entity Word Error Rate Reduction (WERR) of contact names, with and without personal bias in rescorer}
  \label{table:special-tokens}
  \centering

	\begin{tabular}{l | l | r |}
    \toprule
    \multicolumn{2}{c|}{\textbf{LM}} & \multicolumn{1}{c|}{\textbf{Entity}} \\
    \textbf{First-pass} & \textbf{Second-pass}  &   \textbf{WERR(\%)} \\
        \midrule
    KN-4g-Interp-Syn  & - &  - \\
    KN-4g-Interp-Syn & NLM & 9.18\% \\
    KN-4g-Interp-Syn & NLM + bias & 9.56\% \\
    \bottomrule
  \end{tabular}

\end{table}

\section{Conclusions and Future Work}
\label{section:conclusions}
In this work, we addressed several challenges for an NLM to be used in a practical large-scale ASR system. In particular, training an NLM from multiple heterogenous corpora using a novel data mixing strategy, along with transfer learning based on fine-tuning that provided 16.1\% relative improvement in perplexity compared to a baseline trained on in-domain data only. Subsequently, we presented work to limit latency impact of the models. The usage of self-normalized LM helped us to reduce the added latency by 700ms and 3100ms at the 50th and 90th percentiles, compared to using softmax based LMs.  We were able to obtain a 1.6\% relative WERR by generating synthetic data from the NLM and incorporating that into an n-gram model used in the first-pass beam search decoding. Overall, this provided a net WERR of 6.2\% relative along with 10-best rescoring. Finally, we showed that we were able to get accuracy improvements for contact names, using personalized list information, by using classes in the first-pass LM and appropriately handling them in the NLM rescoring through class tags. In the future, we plan to evaluate the data mixing strategy in handling more than two corpora as well as investigating methods for optimizing data mixing weights as part of NLM training procedure.

\bibliographystyle{IEEEtran}