Structures computable in polynomial time. I

DOI10.1007/S10469-017-9416-YMaRDI QIDQ2401536zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Structures computable in polynomial time. II
• Finitely generated structures computable in polynomial time
• scientific article; zbMATH DE number 1956513
• On polynomial time computation over unordered structures
• scientific article; zbMATH DE number 3869313
• Structure of polynomial-time approximation
• Polynomial-time hierarchies on some classes of functions. I
• Definable Subsets of Polynomial-Time Algebraic Structures
• scientific article; zbMATH DE number 1870419
• A time-space hierarchy between polynomial time and polynomial space

Cites work

• scientific article; zbMATH DE number 58131 (Why is no real title available?)
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• scientific article; zbMATH DE number 1534573 (Why is no real title available?)
• Algebraic structures computable without delay
• Complexity and categoricity
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Existence and uniqueness of structures computable in polynomial time
• Polynomial-time Abelian groups
• Polynomial-time versus recursive models

Cited in

(29)

• Definable Subsets of Polynomial-Time Algebraic Structures
• Polynomially computable structures with finitely many generators
• A structure of punctual dimension two
• Constructing punctually categorical semigroups
• The algebraic structure of the isomorphic types of tally, polynomial time computable sets
• Polynomial computability of fields of algebraic numbers
• Effective categoricity of automatic equivalence and nested equivalence structures
• Fields of algebraic numbers computable in polynomial time. II
• Structures computable in polynomial time. II
• Perfect Local Computability and Computable Simulations
• Categoricity for primitive recursive and polynomial Boolean algebras
• Primitive recursive fields and categoricity
• Punctual dimension of algebraic structures in certain classes
• Non-density in punctual computability
• Graphs are not universal for online computability
• Punctual copies of algebraic structures
• Online presentations of finitely generated structures
• A criterion for P-computability of structures
• The complexity of inversion in groups
• Locally Computable Structures
• Primitively recursive categoricity for unars and equivalence structures
• Fields of algebraic numbers computable in polynomial time. I
• scientific article; zbMATH DE number 7407778 (Why is no real title available?)
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Finitely generated structures computable in polynomial time
• Primitively recursively categorical linear orderings
• Complexity issues for the iterated \(h\)-preorders
• Quotient structures and groups computable in polynomial time
• Searching for applicable versions of computable structures

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

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