| 總結: | <p>In this thesis, we study 3-manifolds from an algorithmic point of view. Our motivation is the conjecture that 3-manifold homeomorphism is in <strong>NP</strong>. The hope is that if one can prove this conjecture in the special case of geometric 3-manifolds, then one can use geometrisation to prove the general statement. This thesis predominantly concerns itself with the Seifert fibered case.</p>
<p>The idea is to show that we can bound the size of characteristic topological structures in an arbitrary triangulation. To that end, we first study the size of minimal triangulations of Seifert fibered spaces. We show that we can realise certain important curves, the <em>singular fibres</em>, as subcomplexes by increasing the size of an arbitrary triangulation by a linear factor. We use this result to give bounds on the <em>triangulation complexity</em> of Seifert fibered spaces with non-empty boundary, which is the minimum number of tetrahedra in a triangulation of a manifold. We give a formula for the triangulation complexity which is correct up to a multiplicative factor. We also give an optimal bound for the triangulation complexity of a connect sum.</p>
<p>We then turn our attention to the 3-manifold homeomorphism problem. We first show that recognising (closed) Euclidean and Nil 3-manifolds, and deciding if a given set of Seifert data is correct for them, is in NP. We then consider the case of recognising Seifert fibered spaces with non-empty boundary. We prove that the recognition problem for Seifert fibered spaces with non-empty boundary is in NP, and that deciding whether a given Seifert fibered space with non-empty boundary admits certain Seifert data is in NP ∩ co-NP. To do this, we give bounds on the size of a complete collection of normal annuli in such a Seifert fibered space. The technique we use for this bound, which is the theory of normal surfaces in <em>split</em> handle structures, comprises half this chapter and can be used generally to give a bound of the form c|T|² on the weight of a complete collection of (disjoint) incompressible normal surfaces in an arbitrary triangulation T.</p>
|
|---|