|
This article is cited in 8 scientific papers (total in 8 papers)
Finitely generated structures computable in polynomial time
P. E. Alaev Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Abstract:
We give some simple description for the finitely generated structures with P-computable isomorphic presentation; i.e., presentation computable in polynomial time. The description is close to the formulation of a Remmel and Friedman theorem. We prove that each finitely generated substructure of a P-computable structure also has a P-computable presentation. The description is applied to the classes of finitely generated semigroups, groups, unital commutative rings and fields, as well as ordered unital commutative rings and fields. We prove that every finitely generated commutative ring or a field has a P-computable presentation.
Keywords:
computable structure, polynomial computability, algorithm complexity, semigroup, group, ring, field.
Received: 18.12.2021 Revised: 23.04.2022 Accepted: 15.06.2022
Citation:
P. E. Alaev, “Finitely generated structures computable in polynomial time”, Sibirsk. Mat. Zh., 63:5 (2022), 953–974; Siberian Math. J., 63:5 (2022), 801–818
Linking options:
https://www.mathnet.ru/eng/smj7706 https://www.mathnet.ru/eng/smj/v63/i5/p953
|
|