Skip to main content
MathOverflow

Return to Answer

Added clarification about metric (cf. the comments).
Source Link
Stefan Kohl ♦
Stefan Kohl ♦
  • 19.6k
  • 21
  • 75
  • 137

As to your general question, there is a method which is better than the inefficient solution you give. -- Namely, compute spheres of radii $r = 1, 2, \dots$ with respect to the word metric about the identity and about about the element $m$ to be factored factored, until these spheres intersect nontrivially nontrivially. This way you always get get the shortest possible word as desired, and and depending on the structure of of your group, you save a significant amount of of runtime and memory. Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ about each of $1$ and $m$ at a time, which further reduces memory requirements -- how much, depends again on the structure of your qroup.

That said, in general the runtime- and memory requirements of this method are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you can do much better in general, as the problem of finding a word of minimal length is already hard for finite permutation groups (popular example: solving the Rubik's Cube with the smallest possible number of moves).

As to your general question, there is a method which is better than the inefficient solution you give. -- Namely, compute spheres of radii $r = 1, 2, \dots$ about the identity and about the element $m$ to be factored, until these spheres intersect nontrivially. This way you always get the shortest possible word as desired, and depending on the structure of your group, you save a significant amount of runtime and memory. Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ about each of $1$ and $m$ at a time, which further reduces memory requirements -- how much, depends again on the structure of your qroup.

That said, in general the runtime- and memory requirements of this method are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you can do much better in general, as the problem of finding a word of minimal length is already hard for finite permutation groups (popular example: solving the Rubik's Cube with the smallest possible number of moves).

As to your general question, there is a method which is better than the inefficient solution you give. -- Namely, compute spheres of radii $r = 1, 2, \dots$ with respect to the word metric about the identity and about the element $m$ to be factored, until these spheres intersect nontrivially. This way you always get the shortest possible word as desired, and depending on the structure of your group, you save a significant amount of runtime and memory. Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ about each of $1$ and $m$ at a time, which further reduces memory requirements -- how much, depends again on the structure of your qroup.

That said, in general the runtime- and memory requirements of this method are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you can do much better in general, as the problem of finding a word of minimal length is already hard for finite permutation groups (popular example: solving the Rubik's Cube with the smallest possible number of moves).

Source Link
Stefan Kohl ♦
Stefan Kohl ♦
  • 19.6k
  • 21
  • 75
  • 137

As to your general question, there is a method which is better than the inefficient solution you give. -- Namely, compute spheres of radii $r = 1, 2, \dots$ about the identity and about the element $m$ to be factored, until these spheres intersect nontrivially. This way you always get the shortest possible word as desired, and depending on the structure of your group, you save a significant amount of runtime and memory. Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ about each of $1$ and $m$ at a time, which further reduces memory requirements -- how much, depends again on the structure of your qroup.

That said, in general the runtime- and memory requirements of this method are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you can do much better in general, as the problem of finding a word of minimal length is already hard for finite permutation groups (popular example: solving the Rubik's Cube with the smallest possible number of moves).