|
|||||
|
|
|
|
|
|
|
|
|
On
the complexity of immersed normal surfaces
Benjamin A Burton, Éric Colin de Verdière and Arnaud de Mesmay |
|
Geometry & Topology 20 (2016) 1061–1083
|
Abstract |
|
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. |
Keywords
low-dimensional topology, normal surface, immersed normal
surface, constraint satisfaction problem, three-manifold,
computational complexity
|
Mathematical Subject Classification 2010
Primary: 57N10, 68Q17
Secondary: 57Q35, 68U05
|
References |
Publication
Received: 16 October 2014
Accepted: 28 June 2015
Published: 28 April 2016
Proposed: Cameron Gordon
Seconded: Dmitri Burago, Bruce Kleiner
|
Authors |
| Benjamin A Burton | |
| School of Mathematics and
Physics The University of Queensland Brisbane QLD 4072 Australia |
|
| http://www.maths.uq.edu.au/~bab/ | |
| Éric Colin de Verdière | |
| Département d’informatique École normale supérieure, CNRS 45 rue d’Ulm 75005 Paris France |
|
| http://www.di.ens.fr/~colin/ | |
| Arnaud de Mesmay | |
| CNRS GIPSA-lab 11 rue des Mathématiques Grenoble Campus BP46 F-38402 Saint Martin-d’Hères France |
|
| http://www.gipsa-lab.fr/~arnaud.demesmay | |
|
