kakia
Reputation
Next privilege 100 Rep.
Edit community wikis
 Jul 19 revised Unique Nash equilibrium games one more reference given Jul 7 awarded Enthusiast Jun 24 revised Unique Nash equilibrium games Links to corresponding articles added Jun 21 revised Unique Nash equilibrium games added 84 characters in body; edited tags Jun 19 asked Unique Nash equilibrium games Jul 3 comment Number of Configurations in the optimal Hanoi tower "It seems forcing the number of disks on all 3 towers specifies a unique position" _ this seems to imply that $2^n \in O(n^3)$ :) Jun 25 awarded Informed May 2 revised Number of Configurations in the optimal Hanoi tower added 450 characters in body; edited tags; edited title May 2 comment Number of Configurations in the optimal Hanoi tower Well, 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. Apr 30 awarded Critic Apr 30 asked Number of Configurations in the optimal Hanoi tower Jan 11 awarded Editor Jan 11 revised computational complexity edited tags; edited title Jan 9 awarded Scholar Jan 9 accepted computational complexity Jan 8 awarded Supporter Jan 8 comment computational complexity I 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. Jan 8 awarded Autobiographer Jan 8 revised computational complexity edited tags Jan 8 revised computational complexity edited tags