On the hardness of finding normal surfaces
share
There are fundamental topological problems, such as unknot recognition and 3-sphere recognition, for which the existence of a polynomial time algorithm remains unknown. A major algorithmic tool behind some of the best known algorithms for these problems is normal surface theory. One of the key operations in normal surface theory is finding a non-trivial normal disc or sphere in a 3-dimensional triangulation. Our first result shows that an algebraic abstraction of this problem is NP-hard, which (assuming P≠NP) suggests that any polynomial time solution will need to exploit some geometric or topological intuition. Another key operation used by many topological problems is to find a vertex normal surface of a certain type. We study two closely-related problems of this type: one we show is polynomial time, and the other we show is NP-complete. Most hardness proofs for knots and 3-manifolds in the literature reduce from satisfiability; our proof reduces from Hamiltonian cycle, and so adds a new style of reduction to the toolbox for computational topologists.
READ FULL TEXT