Sphere recognition lies in NP


We prove that the three-sphere recognition problem lies in the complexity class NP. Our work relies on Thompson's original proof that the problem is decidable [Math. Res. Let., 1994], Casson's version of her algorithm, and recent results of Agol, Hass, and Thurston [ArXiv, 2002].


This paper is a highly reworked version of an older preprint which will not, now, be published. Due to space and time considerations some of the applications of the tightening procedure from that paper (a proof of a lemma of Stocking and a discussion of bridge position for the one-skeleton of zero-efficient triangulations) are not in the current version.

If you have any questions or corrections please contact me via email.

last touched - Jul. 2004
Homepage: To maintainer's homepage.
UIC: Up to the math department webpage.