Structures computable in polynomial time. I

DOI10.1007/s10469-017-9416-yzbMath1420.03104OpenAlexW2597066232MaRDI QIDQ2401536

P. E. Alaev

Publication date: 4 September 2017

Published in: Algebra and Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10469-017-9416-y

zbMATH Keywords

computable structurelocally finite structurepolynomially categorical structurestructure computable in polynomial timeweakly polynomially categorical structure

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items (26)

Constructing punctually categorical semigroups ⋮ Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Fields of algebraic numbers computable in polynomial time. II ⋮ Structures computable in polynomial time. II ⋮ Punctual copies of algebraic structures ⋮ Graphs are not universal for online computability ⋮ A criterion for P-computability of structures ⋮ Effective categoricity of automatic equivalence and nested equivalence structures ⋮ A structure of punctual dimension two ⋮ The complexity of inversion in groups ⋮ Online presentations of finitely generated structures ⋮ Polynomially computable structures with finitely many generators ⋮ Categoricity for primitive recursive and polynomial Boolean algebras ⋮ Polynomial computability of fields of algebraic numbers ⋮ Primitively recursively categorical linear orderings ⋮ Primitive recursive fields and categoricity ⋮ Punctual dimension of algebraic structures in certain classes ⋮ Non-density in punctual computability ⋮ Primitively recursive categoricity for unars and equivalence structures ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Fields of algebraic numbers computable in polynomial time. I ⋮ Finitely generated structures computable in polynomial time ⋮ Unnamed Item ⋮ Complexity issues for the iterated \(h\)-preorders ⋮ Quotient structures and groups computable in polynomial time ⋮ Searching for applicable versions of computable structures

Cites Work

• Existence and uniqueness of structures computable in polynomial time
• Algebraic structures computable without delay
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• Complexity and categoricity
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Structures computable in polynomial time. I