# kakia

 103 Reputation 259 views

## Registered User

 Name kakia Member for 4 months Seen 14 hours ago Website Location Age 23
 May2 revised Number of Configurations in the optimal Hanoi toweradded 450 characters in body; edited tags; edited title May2 comment Number of Configurations in the optimal Hanoi towerWell, I see these connections can be arbitrary and there might be no nice way to show the equivalence. I just wanted to have a closed formula for Hanoi tower configurations, from the computational perspective, formulas I see with the equal sequences can be calculated in linear time with respect to $n$, whilst recurrent formula for Hanoi configurations takes cubic time. Apr30 awarded ● Critic Apr30 asked Number of Configurations in the optimal Hanoi tower Jan11 awarded ● Editor Jan11 revised computational complexityedited tags; edited title Jan9 awarded ● Scholar Jan8 awarded ● Supporter Jan8 comment computational complexityI agree with connected components and retraction of boundary, but after these operations we are still dealing with quite arbitrary structure. We can even make things "easier" and assume that every edge is incident with at most 3 triangles by simple topological transformation. If we consider dual problem, take 1 vertex in each triangle and connect two vertices if their respective triangles share edges, we get: in somewhat special graph we need to find cubic planar 3-connected subgraph(corresponding to triangulation). Finding cubic subgraph in planar graph is NP-complete. I see some connection. Jan8 awarded ● Autobiographer Jan8 revised computational complexityedited tags Jan8 comment computational complexityIf 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/… here you can check what are the Euler characteristics of closed surfaces. Jan8 awarded ● Student Jan8 asked computational complexity