Prikl. Diskr. Mat., 2020, Number 48, Pages 109–124
Historical Records on Discrete Mathematics and its Applications
On the meaning of works by V. M. Khrapchenko
S. B. Gashkova, I. S. Sergeevb
a Lomonosov Moscow State University, Moscow, Russia
b FSUE “Research Institute “Kvant”, Moscow, Russia
The paper surveys main works and results by Valerii Mikhailovich Khrapchenko, who stands among the pioneers of national theoretical cybernetics. Mathematical results by V. M. Khrapchenko can be related to the following five directions: 1) synthesis of parallel adders; 2) relations between the complexity and depth of Boolean formulae; 3) low bounds for complexity of Boolean formulae; 4) synthesis of formulae for symmetric Boolean functions; 5) relation between depth and delay of schemes. Method of low bounds by V. M. Khrapchenko comes into many courses of lectures and into all the main monographies on the complexity of Boolean functions. The description of parallel adder by V. M. Khrapchenko is given in many books attended to rapid arithmetics.
depth, circuit delay, Khrapchenko method, lower complexity bounds, parallel adder, symmetric functions.
PDF file (964 kB)
S. B. Gashkov, I. S. Sergeev, “On the meaning of works by V. M. Khrapchenko”, Prikl. Diskr. Mat., 2020, no. 48, 109–124
Citation in format AMSBIB
\by S.~B.~Gashkov, I.~S.~Sergeev
\paper On the meaning of works by V. M. Khrapchenko
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|