Vol 74, No 1 (2019)

It is proved that for an arbitrary polynomial \(f\left( x \right) \in {\mathbb{Z}_{{p^n}}}\left[ X \right]\) of degree d the Boolean complexity of calculation of one its root (if it exists) equals O(dM(nλ(p))) for a fixed prime p and growing n, where λ(p) = ⌈log₂p⌉, and M(n) is the Boolean complexity of multiplication of two binary n-bit numbers. Given the known decomposition of this number into prime factors n = m₁...m_k, \({m_i} = p_i^{{n_i}}\), i = 1,..., k, with fixed k and primes p_i, i = 1,..., k, and growing n, the Boolean complexity of calculation of one of solutions to the comparison f(x) = 0 mod n equals O(dM(λ(n))). In particular, the same estimate is obtained for calculation of one root of any given degree in the residue ring Z_m. As a corollary, it is proved that the Boolean complexity of calculation of integer roots of a polynomial f(x) is equal to O_d(M(n)), where \(f\left( x \right) = {a_d}{x^d} + {a_{d - 1}}{x^{d - 1}} + ... + {a_0},{a_i} \in \mathbb{Z}\) , |a_i| < 2ⁿ, i = 0,..., d.

The oscillation, rotatability, and wandering characteristic indicators of Lyapunov type are studied for two-dimensional linear homogeneous differential systems determining rotations of the phase plane. A complete set of order relations between them is obtained. For each of those indicators it is established whether it is continuous or discontinuous as a function of the coefficients of the system.

We consider the problem of completeness of systems of automaton functions with operations of superposition and feedback of the formΦ ∪ ν, where Φ ⊆ P₂, and ν is finite. The solution of this problem leads to separation of the lattice of closed Post classes into strong ones (whose presence in the system under consideration guarantees the solvability of the completeness problem of finite bases) and weak ones (whose presence in the system under consideration does not guarantee this solvability). It turns out that the classifications of bases by completeness and A-completeness properties coincide. The paper describes this classification.

We consider the Sturm–Liouville equation

where λ² is a spectral parameter, r and ρ are positive functions while p and q are complex-valued ones. An asymptotic representation for the fundamental system of solutions with respect to the spectral parameter λ → ∞ is obtained in the half-planes Im λ ≥ const and Im λ ≤ const under the following conditions on the coefficients: and the antiderivative is understood in the sense of distributions.