Finitely Generated Structures Computable in Polynomial Time

被引:0
|
作者
P. E. Alaev
机构
[1] Sobolev Institute of Mathematics,
来源
Siberian Mathematical Journal | 2022年 / 63卷
关键词
computable structure; polynomial computability; algorithm complexity; semigroup; group; ring; field; 510.52:510.67:512.5;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:801 / 818
页数:17
相关论文
共 50 条