RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive
Intelligent systems. Theory and applications, 2021 Volume 25, Issue 3, Pages 189–190 (Mi ista320)
Part 3. Mathematical models

On the correspondence between the complexity of the sfe and the number of steps of the Turing machine

M. V. Nosov

Lomonosov Moscow State University

Abstract: The work schematically proves an intuitive fact on the correspondence of the polynomial complexity of the SFE in the basis of the Schaeffer prime polynomial number of steps of the Turing machine. Numerical estimates are given.

Keywords: circuit complexity, Schaeffer's stroke, Turing machine.


© Steklov Math. Inst. of RAS, 2025