Vol 56, No 6 (2018)

We consider a new approach to investigating categoricity of structures computable in polynomial time. The approach is based on studying polynomially computable stable relations. It is shown that this categoricity is equivalent to the usual computable categoricity for computable Boolean algebras with computable set of atoms, and for computable linear orderings with computable set of adjacent pairs. Examples are constructed which show that this does not always hold. We establish a connection between dimensions based on computable and polynomially computable stable relations.

It is known that for any set π of prime numbers, the following assertions are equivalent: (1) in any finite group, π-Hall subgroups are conjugate; (2) in any finite group, π-Hall subgroups are pronormal. It is proved that (1) and (2) are equivalent also to the following: (3) in any finite group, π-Hall subgroups are pronormal in their normal closure. Previously [10, Quest. 18.32], the question was posed whether it is true that in a finite group, π-Hall subgroups are always pronormal in their normal closure. Recently, M. N. Nesterov [7] proved that assertion (3) and assertions (1) and (2) are equivalent for any finite set π. The fact that there exist examples of finite sets π and finite groups G such that G contains more than one conjugacy class of π-Hall subgroups gives a negative answer to the question mentioned. Our main result shows that the requirement of finiteness for π is unessential for (1), (2), and (3) to be equivalent.

Polygons with a (P, 1)-stable theory are considered. A criterion of being (P, 1)-stable for a polygon is established. As a consequence of the main criterion we prove that a polygon _SS, where S is a group, is (P, 1)-stable if and only if S is a finite group. It is shown that the class of all polygons with monoid S is (P, 1)-stable only if S is a one-element monoid. (P, 1)-stability criteria are presented for polygons over right and left zero monoids.