Recognizing the 3-sphere (Q1347363)

The author gives a new version of the Rubinstein-Thompson recognition algorithm for the 3-sphere [\textit{J. H. Rubinstein}, AMS/IP Stud. Adv. Math. 2 (Pt. 1), 1-20 (1997; Zbl 0889.57021); \textit{A. Thompson}, Math. Res. Lett. 1, No. 5, 613-630 (1994; Zbl 0849.57009)], based on the notions of \(Q\)-triangulation and \(A1\)-normal surface. The setting is that of closed orientable 3-manifolds \(M\) given by cell decompositions \(\Omega\), whose closed 3-cells are polyhedra (3-balls with a cell decomposition of their boundaries) and have dimension preserving cellular characteristic maps. A surface \(S \subset M\) in general position with respect to \(\Omega\) is called normal if, for every closed 3-cell \(C\) of \(\Omega\), \(S \cap C\) consists of regularly embedded disks \(D \subset C\), such that \(\partial D\) is not contained in any 2-cell of \(\partial C\) and crosses each 1-cell at most once. \(S\) is called \(A1\)-normal if the condition above on \(\partial D\) is satisfied by all the disks \(D\) but one (in all of \(S\)), and the boundary of the exceptional disk crosses each 1-cell at most twice, with a technical restriction on the order of the crossings. A \(Q\)-triangulation is a cell decomposition \(\Omega\) such that: 1) the closed 3-cells of \(\Omega\) are all tetrahedra or degenerate tetrahedra (with 3 vertices, 2 triangle and some biangle faces); 2) \(\Omega\) has only one 0-cell \(V\); 3) the link \(\text{lk}(V,\Omega)\) is a normal 2-sphere. \(\Omega\) is called irreducible if any normal 2-sphere is normally parallel to \(\text{lk}(V,\Omega)\). By the main result of the paper, a closed orientable 3-manifold \(M\), given by an irreducible \(Q\)-triangulation, is a 3-sphere iff it contains an \(A1\)-normal 2-sphere \(S\) (in fact, \(S\) splits \(M\) into two 3-balls). Then, starting from any triangulation \(\Omega\) of \(M\), the recognition algorithm consists of two steps: 1) decompose \(M\) as a connected sum of a certain number of copies of \(S^1 \times S^2\) and some other 3-manifolds \(M_1, \dots, M_k\), with given irreducible \(Q\)-triangulations \(\Omega_1, \dots, \Omega_k\); 2) look for \(A1\)-normal 2-spheres in the \(M_i\)'s, to check whether they are 3-spheres. The complexity of these steps is also investigated, by showing that both the following problems are in NP: 1) find a non-trivial normal 2-sphere in a reducible \(Q\)-triangulation; 2) establish whether a 3-manifold given by an irreducible \(Q\)-triangulation is a 3-sphere.