Sphere Recognition is in NP
by
Saul Schleimer
University of Illinois at Chicago

A canonical compression body in a triangulated three-manifold is an embedded compression body with the positive boundary an almost normal surface and negative boundary the "closest" normal surface on that side. We'll give a polynomial time algorithm to decide if a given submanifold is a canonical compression body. There are several consequences: sphere and surface bundle recognition can be preformed in NP-time. This approach should also have applications to the problem of deciding whether or not a surface is a Heegaard splitting.

Date received: March 5, 2002