Structures computable in polynomial time. II

DOI10.1007/s10469-018-9465-xzbMath1420.03105OpenAlexW4245421229MaRDI QIDQ1644852

P. E. Alaev

Publication date: 22 June 2018

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

Full work available at URL: https://doi.org/10.1007/s10469-018-9465-x

zbMATH Keywords

categoricitycomputable categoricitycomputable stable relationspolynomially computable stable relations

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 (13)

Constructing punctually categorical semigroups ⋮ Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Fields of algebraic numbers computable in polynomial time. II ⋮ Punctual copies of algebraic structures ⋮ Graphs are not universal for online computability ⋮ Effective categoricity of automatic equivalence and nested equivalence structures ⋮ A structure of punctual dimension two ⋮ Online presentations of finitely generated structures ⋮ Primitive recursive fields and categoricity ⋮ Punctual dimension of algebraic structures in certain classes ⋮ Non-density in punctual computability ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence and uniqueness of structures computable in polynomial time
• Some properties of algebraic reducibility of constructivizations
• Autostability of models
• Polynomial-time versus recursive models
• Complexity and categoricity
• Algorithmic degree of unars
• Algebraic dependences and reducibilities of constructivizations in universal domains
• Countability of widths of algebraic reducibility structures for models in some classes
• Structures computable in polynomial time. I
• Constructivizable models with a linear structure of algebraic reducibility
• Recursive isomorphism types of recursive Boolean algebras
• Relations Intrinsically Recursive in Linear Orders
• Recursively Categorical Linear Orderings

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