The monograph presents a portion of a genealogical tree of computer scientists in the USSR, along the major branches leading from the three pioneers of mathematical logic: A. Markov, A. Kolmogorov, and P. Novikov. The term “cybernetics” (kibernetika) is used in Soviet terminology. It covers (in its theoretical or mathematical branch) AI, Operations Research, Game Theory, Optimal Control Theory, Mathematical Problems of Bionics, and Theoretical Computer Science (including Theoretical Programming, Automata Theory and Formal Language Theory, Computational Complexity, and Discrete Analysis including Combinational Complexity). The text covers three branches--namely, Finite Automata, Combinational Complexity, and Algorithmic Complexity--from the mid-1950s to the mid-1970s. It includes, in addition, a chapter devoted to the Soviet mathematical establishment and schools and groups in theoretical computer science; a chapter of conclusions; and three appendices.

The author shows that in the USSR many interesting and significant results appeared independently of, in parallel to, and even sometimes prior to similar achievements in the West; to name only a few (a complete story appears in Appendix A written by A. Meyer): gap theorem (Trakhtenbrot/Borodin), Kolmogorov complexity (Kolmogorov-Levin-Zvonkin/Chaitin-Solomonoff), NP-complexity (Levin/Cook-Karp), and probabilistic computation (Barzdin-Freivald/Gill-Rabin-Pippenger-Strassen-Simon).

This book is successfully written by a first-rate teller of these stories, who is known from the early 1950s for his finitary form of the undecidability of first-order logic. It improves our knowledge of Soviet achievements in the field and stimulates further exchanges between East and West.