Search

Under study is the algorithmic complexity of isomorphisms between computable copies of locally finite graphs $ G $ (undirected graphs whose every vertex has finite degree). We obtain the following results: If $ G $ has only finitely many components then $ G $ is $ {\mathbf{d}} $ -computably categorical for every Turing degree $ {\mathbf{d}} $ from the class $ PA({\mathbf{0}}^{\prime}) $ . If $ G $ has infinitely many components then $ G $ is $ {\mathbf{0}}^{\prime\prime} $ -computably categorical. We exhibit a series of examples showing that the obtained bounds are sharp.

We find an exact estimate for the algorithmic complexity of the class of autostable ordered Abelian groups.

We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees.

We obtain an exact bound for the algorithmic complexity of the class of strongly constructivizable computable groups that are autostable relative to strong constructivizations.

We obtain exact estimates for the algorithmic complexity for the classes of strongly constructivizable computable models autostable relative to strong constructivizations and belonging to the following natural classes: Boolean algebras, distributive lattices, rings, commutative semigroups, and partial orders.

This paper calculates, in a precise way, the complexity of the index sets for computable structures that are autostable relative to strong constructivizations and belong to one of the following classes: linear orderings, Boolean algebras, distributive lattices, partial orderings, rings, and commutative semigroups. We also calculate the complexity of the index set for computable structures that have computable dimension n, where n is a fixed natural number greater than 1.