> < ^ From:

> < ^ Subject:

Istvan Hernadvolgyi asked:

I recently downloaded and installed gap. I do not know too much about

the package, but I would like to use it to develop algorithms to solve the

Rubik's Cube and similar puzzles. I would appreciate if someone could

provide a little help, especially if someone already programmed the Cube

or something similar in gap.

The question of course asks to find shortest expressions for a group

element in given generators or equivalently shortest pathes from one

point to another in the Cayley graph of a group. This is known to be

computationally difficult - it falls into one of those nastier

categories of complexity analysis ( I am not an expert on complexity

theory, so do not ask me for more exact terminology). However I know

that there are rather efficient approximative algorithms, one research

group dealing with these are Gene Cooperman and Larry Finkelstein at

Northeastern University, Boston, MA. who say that they have methods by

which they can obtain solutions close to or even better than the best

ones known.

Gene and Larry, can you perhaps comment directly in the Forum?

Reagards Joachim Neubueser

> < [top]