Том 55, № 6 (2017)

It is proved that every computable locally finite structure with finitely many functions has a presentation computable in polynomial time. Furthermore, a structure computable in polynomial time is polynomially categorical iff it is finite. If a structure is computable in polynomial time and locally finite then it is weakly polynomially categorical (i.e., categorical with respect to primitive recursive isomorphisms) iff it is finite.

It is proved that for every natural n ≥ 1, there exists a computable freely generated projective plane with computable dimension n. It is stated that the class of freely generated projective planes is complete with respect to degree spectra of automorphically nontrivial structures, effective dimensions, expansions by constants, and degree spectra of relations.

Two functional clones F and G on a set A are said to be algebraically equivalent if sets of solutions for F- and G-equations coincide on A. It is proved that pairwise algebraically nonequivalent existentially additive clones on finite sets A are finite in number. We come up with results on the structure of algebraic equivalence classes, including an equationally additive clone, in the lattices of all clones on finite sets.