Decision algorithms and normal surfaces in 3-manifolds

The normal system of equations ${\cal N}$(M,${\cal T}$) is derived for a closed, irreducible 3-manifold M having a fixed triangulation ${\cal T}$. Corresponding to each normal surface F, a branched normal surface $B\sb{F}$ is constructed. We show that to determine whether M is Haken, it is sufficient to test the set of branched normal surfaces $B\sb{F}$ associated with the finite set of vertex surfaces F of (M,${\cal T}$) for injectivity. If some $B\sb{F}$ is found to be injective then M is Haken.

We produce an algorithm to test a branched surface $B\sb{F}$ for injectivity. It is shown that if there is an essential punctured compression disk or an essential punctured monogon then such a disk will exist as a vertex surface of ${\cal N}(M\sb\sigma$,${\cal T}\sb\sigma)$, where $M\sb\sigma$ = Cl($M - N(B\sb{F}))$.

A system of equations which is equivalent on admissible vertices to the normal Q-system is found. Computer programs to implement these algorithms were written in connection with this paper.