On the computational complexity of the theory of Abelian groups

DOI10.1016/0168-0072(88)90020-6zbMath0639.03010OpenAlexW1983136104MaRDI QIDQ1100188

Libo Lo

Publication date: 1988

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(88)90020-6

zbMATH Keywords

complexityAbelian groupsdecidabilityfinite Abelian groupsfirst-order theoriesGurevich's conjecturecyclic groups of prime power orderEhrenfeucht gamesdirect sums of countably many infinite cyclic groupsdivisible and indecomposable p-groupsgroups of rational numbers with denominators prime to p

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Abelian groups (20K99)

Related Items

Computational complexity of logical theories of one successor and another unary function, A uniform method for proving lower bounds on the computational complexity of logical theories, Complexity of logical theories involving coprimality, Decidability and modules over Bézout domains

Cites Work

• The computational complexity of logical theories
• An application of games to the completeness problem for formalized theories
• The elementary theory of abelian groups
• On the interval containing at least one prime number
• Elementary properties of Abelian groups
• Unnamed Item
• Unnamed Item
• Unnamed Item