I am interested into computational complexity of decision problem: Does a given 2dimensional simplicial complex contain (any)triangulation of 2sphere? This problem trivially lies into NP, because certificate is the subset of triangles. I think that it is NPcomplete.

$\begingroup$ For those of us who are simplicialsimpletons, could you explain how you verify the certificate in polynomial time? $\endgroup$– Joel David HamkinsJan 8, 2013 at 15:18

$\begingroup$ If we are given set of triangles as a certificate, first we will check connectivity, afterwards we check that the link of each vertex is a cycle. If these conditions are satisfied, we know for sure that we have a closed surface. Then calculate Euler characteristic, we are dealing with sphere if and only if Euler characteristic is 2. en.wikipedia.org/wiki/Surface#Classification_of_closed_surfaces here you can check what are the Euler characteristics of closed surfaces. $\endgroup$– kakiaJan 8, 2013 at 15:32

$\begingroup$ Thanks very much! Would it be possible to give an example of the kind of difficult case you imagine? Or even merely a noncompletelytrivial case, where a decision is made because of some global feature, rather than merely a local oneif all decisions are local, I expect it in P. Given a simplicial complex, we can reduce to its connected components, and we can seem to retract any boundaries, right? What kind of complexes are we left with? I apologize for my naive questions, but I find the topic interesting, and as I am currently the sole upvoter, I feel free to inquire. $\endgroup$– Joel David HamkinsJan 8, 2013 at 22:13

$\begingroup$ Ah, good, I see now that I am joined by other upvoters... $\endgroup$– Joel David HamkinsJan 8, 2013 at 22:21

2$\begingroup$ Complexes to worry about are something like Bing's "house with two rooms" which is a 2dimensional complex which is contractible but not collapsible. In particular, "Bing's house" contains no embedded 2spheres, but has no "boundaries" to retract. Of course, you can detect absence of 2spheres by looking at 2nd homology, but this example shows that one needs further global considerations. $\endgroup$– MishaJan 8, 2013 at 23:28
1 Answer
It is NPcomplete. Here is a reduction from the graph 3coloring problem.
For a given graph, consider a sphere with $n$ holes where $n$ is the number of vertices. Enumerate the holes by the vertices of the graph. Fill each hole by 3 discs (red, green and blue) by identifying each disc boundary with the hole boundary. Glue the centers of the 3 discs into one point (so that nor two of them cannot be included in one surface), Then, for every edge of the graph, pick one new point in each of the 6 discs filling the holes corresponding to the edge endpoints, and glue together each of the 3 pairs of chosen points lying on discs of the same color. The points chosen for different edges must be distinct.
The resulting topological space is homeomorphic to a simplicial complex (which is easy to construct from the graph in polynomial time). It contains a sphere if and only if the original graph is 3colorable.
Remark. You can alter the formulation by saying that an immersed sphere which selfintersects itself in finitely many points is still a sphere. For this problem, the construction can be modified as follows. To make a pair of discs "forbidden", glue together two pairs of small discs in them rather than one pair of point. This creates a surface of positive genus if you try to pick a pair of discs connected this way.

$\begingroup$ In your construction, wouldn't two discs filling the same hole form a 2sphere already? $\endgroup$ Jan 9, 2013 at 9:19

$\begingroup$ I see. This likely works, though I admit I couldn't tell how to prove that the complex can't accidentally contain a sphere. Interesting. $\endgroup$ Jan 9, 2013 at 13:29