  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.
