tag:blogger.com,1999:blog-3722233.post5070159997037600411..comments2022-05-24T23:04:24.301-05:00Comments on Computational Complexity: The Complexity of Rubik's CubeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-10068184304389276232017-07-12T22:01:37.649-05:002017-07-12T22:01:37.649-05:00I would say the point is the difference between &q...I would say the point is the difference between "solving the Cube problem" and "solving the shortest solution problem". No whiz-kid can, on promise that there is a 19-move solution, find it within 30 seconds...KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2365887778702485952017-07-05T12:52:56.420-05:002017-07-05T12:52:56.420-05:00Coloring the edges of a graph is also easy, even w...Coloring the edges of a graph is also easy, even with only one color more than necessary, but to decide whether \Delta or \Delta + 1 colors are needed is NP-hard. Here the gap is probably narrower than for Rubik's cube.HAJDUKhttp://rolandglueck.de/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58851413194298560392017-07-05T07:38:22.099-05:002017-07-05T07:38:22.099-05:00Reminds me of the various sorting-by-transposition...Reminds me of the various sorting-by-transposition questions: <br />sorting is easy/efficient, one can always do it in O(n) steps, but finding the shortest sequence of sorting moves is NP-hard and often hard to approximate as well. Meenahttps://www.blogger.com/profile/00370241251541994963noreply@blogger.com