Reply to post: Re: Algorithm./ Technique

How to solve a Rubik's Cube in five seconds


Re: Algorithm./ Technique

There are a lot of problems in which is it intractable to have an optimal solution, but sub-optimal solutions are very tractable. A good example of this is the Travelling Salesman Problem - which is known to be NP-Complete. However, if one accepts that we can accept a solution which is less than or equal to twice the optimal solution, this problem becomes tractable.

Although there may be an algorithm that will solve the cube in 20 moves, the one which solves it in 40 may be quicker from a computational point of view.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2019