Polynomial-time Abelian groups (Q1192353): Difference between revisions

The authors continue to study subrecursive presentations of algebraic structures along the lines of their earlier paper [ibid. 54, 17-58 (1991; Zbl 0756.03021)] and that of \textit{S. Grigorieff} [J. Symb. Logic 55, 260- 276 (1990; Zbl 0708.03015)]. In particular, the authors study the extent to which torsion abelian groups can be presented so that the underlying set and operations are polynomial-time computable. The particular concern of the paper is comparisons and tensions between classical isomorphism types, recursive isomorphism types, and polynomial isomorphism types. For instance, it is shown that any recursive abelian torsion group is recursively isomorphic to a p-time one (Theorem 4.7). Refinements of the notion of presentation such as demanding that the universe is a tally set or \(\{0,1\}^*\) are analysed. Technically, the key tools are the use of algebraic techniques such as the Ulm sequence, padding type techniques, as well as wait-and-see arguments for the negative results. The results can be seen as a modern ``p-time'' extension of earlier work of \textit{R. L. Smith} [e.g. Logic Year 1979-80, Lect. Notes Math. 859, 302-311 (1981; Zbl 0488.03024)] and Charlotte Lin on recursive abelian groups, following a tradition going back to Metakides-Nerode, Rabin, Frolich-Shepherdson, van der Waerden, and others.