Finitely Generated Structures Computable in Polynomial Time
Author:
- 1 September 2022
- journal article
- research article
- Published by Pleiades Publishing Ltd in Siberian Mathematical Journal
- Vol. 63 (5) , 801-818
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
This publication has 10 references indexed in Scilit:
- Fields of algebraic numbers computable in polynomial time. IAlgebra i logika, 2019
- Categoricity for Primitive Recursive and Polynomial Boolean AlgebrasAlgebra and Logic, 2018
- Algebraic structures computable without delayTheoretical Computer Science, 2017
- Structures Computable in Polynomial Time. IAlgebra and Logic, 2017
- Ideal membership in polynomial rings over the integersJournal of the American Mathematical Society, 2004
- Chapter 10 Complexity theoretic model theory and algebra1998
- Some Complexity Results for Polynomial IdealsJournal of Complexity, 1997
- Polynomial-time versus recursive modelsAnnals of Pure and Applied Logic, 1991
- Some algorithmic problems for solvable groupsAlgebra and Logic, 1974
- CONSTRUCTIVE ALGEBRAS IRussian Mathematical Surveys, 1961