  For many fundamental problems in computational topology, such as unknot
recognition and $3$-sphere recognition, the existence of a polynomial-time
solution remains unknown. A major algorithmic tool behind some of the best
known algorithms for these problems is normal surface theory. However, we
currently have a poor understanding of the computational complexity of problems
in normal surface theory: many such problems are still not known to have
polynomial-time algorithms, yet proofs of $\mathrm{NP}$-hardness also remain
scarce. We give three results that provide some insight on this front.
  A number of modern normal surface theoretic algorithms depend critically on
the operation of finding a non-trivial normal sphere or disc in a
$3$-dimensional triangulation. We formulate an abstract problem that captures
the algebraic and combinatorial aspects of this operation, and show that this
abstract problem is $\mathrm{NP}$-complete. Assuming
$\mathrm{P}\neq\mathrm{NP}$, this result suggests that any polynomial-time
procedure for finding a non-trivial normal sphere or disc will need to exploit
some geometric or topological intuition.
  Another key operation, which applies to a much wider range of topological
problems, involves finding a vertex normal surface of a certain type. We study
two closely-related problems that can be solved using this operation. For one
of these problems, we give a simple alternative solution that runs in
polynomial time; for the other, we prove $\mathrm{NP}$-completeness.
