Finitely generated structures computable in polynomial time

DOI10.1134/S0037446622050019MaRDI QIDQ2088618zbMATH OpenOpenAlexFDO

Authors P. E. Alaev

Publication date 6 October 2022

Published in Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0037446622050019

zbMATH Keywords

algorithm complexitycomputable structurefieldgrouppolynomial computabilityringsemigroup

Mathematics Subject Classification ID

Model theory (03Cxx) Computability and recursion theory (03Dxx) Computational aspects and applications of commutative rings (13Pxx)

Recommendations

• Structures computable in polynomial time. I
• STACS 2005
• Polynomial-time versus recursive models
• Fields of algebraic numbers computable in polynomial time. II
• Finitely generated groups are universal among finitely generated structures

Cites work

• Algebraic structures computable without delay
• Categoricity for primitive recursive and polynomial Boolean algebras
• CONSTRUCTIVE ALGEBRAS I
• Fields of algebraic numbers computable in polynomial time. I
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• Ideal membership in polynomial rings over the integers
• Polynomial-time versus recursive models
• Some algorithmic problems for solvable groups
• Some complexity results for polynomial ideals
• Structures computable in polynomial time. I

Cited in

(8)

• Structures computable in polynomial time. I
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• A criterion for P-computability of structures
• Punctually presented structures I: Closure theorems
• The complexity of inversion in groups
• Lower bounds for the rank of a matrix with zeros and ones outside the leading diagonal
• Description of structures computable in polynomial time
• Punctually presented structures. II: Comparing presentations.

This page was built for publication: Finitely generated structures computable in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2088618)