On the Complexity of Immersed Normal Surfaces

Normal surfaces are a ubiquitous tool in computational 3-manifold theory. In this paper, we investigate a relaxed notion of normal surfaces where we remove the quadrilateral conditions. This yields normal surfaces that are no longer embedded. We prove that it is NP-hard to decide whether a given singular normal surface is immersed. Our proof uses a reduction from boolean constraint satisfaction problems where every variable appears in at most two clauses, using a classification theorem of Feder