Word problem for symmetric group is linear on RAM
1 Linear time algorithm for symmetric group
Input: is a word of length from the presentation where .
true if is the identity, else return
The representation was crucial for coming up with a linear time algorithm respect to and . This is not a word problem on one group, but on a set of group.
The following is a algorithm for the word problem for symmetric groups on RAM.
- Produce an array
aof size , Such that
a[i] = i. (Array start with index 1)
- Reading the word letter by letter. If one encounters ,
- Test if the
a[i] == ifor all . If true, return
true, else return
The algorithm takes time is obvious. The correctness needs to be justified.
can be represented as the transposition . Define .
Represent a element of the group as a permutation in the 2 line notation. wlog, assume and .
If we call the index of if . Then each transposition is a swap of indices.
The value of
a[i] in the algorithm stores the index of . Array
a represent the identity iff
a[i] = i for all .
This proves the the correctness of the algorithm.
The algorithm can be modified so it runs in time for a Turing machine. For each fixed , a Turing machine can construct another Turing machine , such that it store the state of the array as the state of the Turing machine.
This proves every symmetric group is automatic. For any fixed , the Turing machine can solve the problem in time without writing anything to the tape and can only move to the right, which is equivalent to a finite state automata.
Automatic is a property of a group, not a set of groups. That's why is ignored in the , because it's fixed for each . I was confused for a while before I read a concrete definition.
2 Algorithms on reduce the word to normal form
The normal form of a word is , such that , and .
One can construct a purely symbolic algorithm that apply only the group relations. We measure the time by the amount of group relations used.
Siegel proposed an algorithm to solve this problem.
If there exist an algorithm that write the word of length in normal form in time., then one can always make it into an algorithm taking time.
Observe that where and are words in normal form, and the length of is maximized. . Here can be worst case, one single letter, it doesn't change the complexity. Let's introduce two algorithms. A' and A''.
first find the in the description, then returns the value of , where .
Recursively calculate with the following definition. . , where .
and runs in time.
can ran at most times, each time it makes a call to , contribute the factor .
In particular, Siegel's algorithm can be modified to run in time.