Description of structures computable in polynomial time

DOI10.1016/J.APAL.2025.103636MaRDI QIDQ6912202zbMATH OpenFDO

Authors P. E. Alaev

Publication date 23 October 2025

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.APAL.2025.103636

zbMATH Keywords

computabilitycomputable structurepolynomial computabilitypolynomially computable structure

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Complexity of computation (including implicit computational complexity) (03D15) Torsion-free groups, infinite rank (20K20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• A criterion for P-computability of structures
• Algebraic structures computable without delay
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Fields of algebraic numbers computable in polynomial time. I
• Finitely generated structures computable in polynomial time
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• Independence in computable algebra
• Polynomial-time Abelian groups
• Polynomial-time versus recursive models
• Quotient structures and groups computable in polynomial time
• Space complexity of abelian groups
• Structures computable in polynomial time. I
• The complexity of inversion in groups

Cited in

(1)

• The existence of primitive recursive structures

This page was built for publication: Description of structures computable in polynomial time

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