Some conditionally hard problems on links and 3-manifolds (Q2411821)

This paper is an investigation of the computational complexity of three problems in 3-dimensional topology. The first problem concerns the Thurston complexity of an unoriented link in the 3-sphere. Given a link and a positive integer, the problem is to decide whether or not there exists a Seifert surface for the link whose Thurston norm is less than the given integer. This problem is shown to be NP-complete. (Recall that the Thurston norm of a compact, oriented surface is the sum of the norms of its connected components where the norm of a connected component is defined to be the maximum of 0 and the negative of its Euler characteristic.) The second problem is the homeomorphism problem for closed 3-manifolds, that is, to decide whether or not two given triangulated closed 3-manifolds are homeomorphic. It is proved that the graph isomorphism problem is reducible to the homeomorphism problem for closed 3-manifolds. Thus the homeomorphism problem is at least as hard as the graph isomorphism problem which at present is not known to be solvable in polynomial time. The sublink problem is the third problem, that is, given two link diagrams to decide whether or not the first link is equivalent to a sublink of the second. It is shown that the problem of determining whether a finite graph has a Hamiltonian path is reducible to the sublink problem. Consequently the sublink problem is NP-hard.