\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}
