# computational complexity

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

• For those of us who are simplicial-simpletons, could you explain how you verify the certificate in polynomial time? Jan 8 '13 at 15:18
• 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. Jan 8 '13 at 15:32
• Thanks very much! Would it be possible to give an example of the kind of difficult case you imagine? Or even merely a non-completely-trivial case, where a decision is made because of some global feature, rather than merely a local one---if 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 up-voter, I feel free to inquire. Jan 8 '13 at 22:13
• Ah, good, I see now that I am joined by other up-voters... Jan 8 '13 at 22:21
• Complexes to worry about are something like Bing's "house with two rooms" which is a 2-dimensional complex which is contractible but not collapsible. In particular, "Bing's house" contains no embedded 2-spheres, but has no "boundaries" to retract. Of course, you can detect absence of 2-spheres by looking at 2-nd homology, but this example shows that one needs further global considerations. Jan 8 '13 at 23:28

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.