On the Computational Complexity of the Theory of Abelian Groups.
Libo Lo · Deep Blue (University of Michigan) · 1984
The existing results about the computational complexity of the theory of the direct sum of countably many infinite cyclic groups and the theory of finite Abelian groups were given by Ferrante and Rackoff. The results are as follows: 2('2('2('cn))) Turing space units suffice to decide a first order sentence with quantifier-depth n in these two theories. Professor Gurevich conjectured that the first order theory of all Abelian groups is elementary and suggested that the author work on this problem as his doctoral dissertation at The University of Michigan. This conjecture is confirmed in this paper. We develop a series of Ehrenfeucht games and prove the following results: (i) The first order theory of the divisible and indecomposable p-group, the first order theory of the group of rational numbers with denominators prime to p and the first order theory of a cyclic group of prime power order can be decided in 2('2('cnlogn)) Turing time. (ii) The first order theory of the direct sum of countably many infinite cyclic groups, the first order theory of finite Abelian groups and the first order theory of all Abelian groups can be decided in 2('2('dn)) Turing space.