In this paper we outline several algorithms to find essential surfaces in 3-dimensional manifolds. In particular, the classical decomposition theorems of 3-manifolds (Kneser–Milnor connected sum decomposition and the JSJ decomposition) are defined by splitting along families of disjoint essential spheres and tori. We give algorithms to find such surfaces, using normal and almost normal surface theory and the technique of crushing triangulations. These algorithms have running time \( O(p(t)3^t) \), where \( t \) is the number of tetrahedra in any given initial one-vertex triangulation of the manifold and \( p(t) \) is some polynomial in \( t \). A special instance of these ideas gives a new algorithm also with running time \( O(p(t)3^t) \) for deciding if a knot is the unknot, where \( t \) is the number of tetrahedra
in an ideal triangulation of the knot complement. Note that there is a bound \( t \leq cn \), where \( n \) is the crossing number of a projection of the knot and \( c \) is a (small) constant. We discuss this in detail elsewhere. Note that these algorithms avoid the computationally more expensive issue of deciding whether a given surface is incompressible.
Our other main algorithm is to determine if a given 3-manifold has an embedded incompressible surface or not. If the manifold is known to be irreducible (by applying our first algorithm), then this is the same as determining if it is Haken or not. As Thurston’s uniformisation theorem applies to the class of Haken 3-manifolds, this is a key algorithmic issue in 3-manifold theory. In particular, few examples are known of non-Haken 3-manifolds and we hope that this algorithm will be useful for finding new ones.
This algorithm has running time \( O(k^t) \), where \( k \) is a constant. We will give a rough upper bound on \( k \) and in another paper discuss some lower bounds for various important quantities involved in normal and almost normal surface theory.
A. Casson gave inspirational lectures at Montreal in 1995 and at the Technion in 1999 on related topics. In particular he outlined an approach to the problem of finding the connected sum decomposition in the latter talk and introduced linear programming as a key tool. He also described crushing normal surfaces in the former talk, as a way of simplifying triangulations. We will discuss his method and compare it to ours.
