It is proved that the uniform word problem for commutative semigroups of dimension k (shortly, UWP(k)) is complete for the symmetric linear space in the case of k≥; UWP(1) is solvable in polynomial time. Also, the author announces that UWP(4) is NP-hard and states that the complexity of UWP(k), k &egr; {2, 3, 5} is not known.
The proof uses the symmetric Turing machines and consists of a series of clever reductions. The paper is self-contained.
