On the complexity of immersed normal surfaces. (English) Zbl 1339.68258

Burton, Benjamin; Colin de Verdière, Éric; de Mesmay, Arnaud

Geom. Topol. 20, No. 2, 1061-1083 (2016).

Summary: Normal surface theory, a tool to represent surfaces in a triangulated 3-manifold combinatorially, is ubiquitous 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 such a 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. We also investigate variants, and provide a polynomial-time algorithm to test for a local version of this problem.

MSC:

68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
57N10	Topology of general \(3\)-manifolds (MSC2010)
57Q35	Embeddings and immersions in PL-topology
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25	Analysis of algorithms and problem complexity

Keywords:

low-dimensional topology; normal surface; computational complexity; computational 3-manifold theory; Boolean constraint satisfaction; polynomial-time algorithm