RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2022 Volume 63, Number 5, Pages 953–974 (Mi smj7706)

This article is cited 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.

UDC: 510.52+510.67+512.5

MSC: 35R30

Received: 18.12.2021
Revised: 23.04.2022
Accepted: 15.06.2022

DOI: 10.33048/smzh.2022.63.501


 English version:
Siberian Mathematical Journal, 2022, 63:5, 801–818

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025