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.
Download file
Counter downloads: 156
- Title On the meaning of works by V. M. Khrapchenko
- Headline On the meaning of works by V. M. Khrapchenko
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 48
- Date:
- DOI 10.17223/20710410/48/10
Keywords
глубина схем, задержка схем, метод Храпченко, нижние оценки сложности, параллельный сумматор, симметрические функции, depth, circuit delay, Khrapchenko method, lower complexity bounds, parallel adder, symmetric functionsAuthors
References
Храпченко В. М. Об одном способе преобразования многорядного кода в однорядный // Доклады АН СССР. 1963. Т.148. №2. C. 296-299
Храпченко В. М. Об оценке погрешности двоичного умножения // Проблемы кибернетики. Вып. 10 / ред. А. А. Ляпунов. М.: Наука, 1963. C. 165-177.
Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. Вып. 19 / ред. А. А. Ляпунов. М.: Наука, 1967. C. 107-120.
Яблонский С. В., Козырев В. П. Математические вопросы кибернетики // Информационные материалы Научного совета по комплексной проблеме «Кибернетика» АН СССР. Вып. 19а. М., 1968. C.3-15.
Храпченко В. М. О сложности реализации линейной функции в классе П-схем // Математические заметки. 1971. Т. 9. №1. C. 35-40.
Храпченко В. М. Об одном методе получения нижних оценок сложности П-схем // Математические заметки. 1971. Т. 10. №1. C. 83-92.
Храпченко В. М. О сложности реализации симметрических функций формулами // Математические заметки. 1972. Т. 11. №1. C. 109-120.
Храпченко В. М. Квадратичная нижняя оценка сложности, основанная на непрерывности второй производной // Проблемы кибернетики. Вып. 26 / ред. А. А. Ляпунов. М.: Наука, 1973. C. 203-206.
Храпченко В. М. О сложности реализации симметрических функций алгебры логики формулами в конечных базисах // Проблемы кибернетики. Вып. 31 / ред. С.В. Яблонский. М.: Наука, 1976. C. 231-234.
Храпченко В. М. Некоторые оценки для времени умножения // Проблемы кибернетики. Вып. 33 / ред. С. В. Яблонский. М.: Наука, 1978. C. 221-227.
Храпченко В. М. Глубина и задержка схемы // Доклады АН СССР. 1978. Т. 241. №6. C. 1281-1284.
Храпченко В. М. О соотношении между сложностью и глубиной формул // Методы дискретного анализа в синтезе управляющих систем. Вып. 32. Новосибирск: ИМ СО АН СССР, 1978. C. 76-94.
Храпченко В. М. Различие и сходство между задержкой и глубиной // Проблемы кибернетики. Вып. 35 / ред. С. В. Яблонский. М.: Наука, 1979. C. 141-168.
Храпченко В. М. О соотношении между сложностью и глубиной формул в базисе, содержащем медиану // Методы дискретного анализа в изучении булевых функций и графов. Вып.37. Новосибирск: ИМ СО АН СССР, 1981. C. 77-84.
Храпченко В. М. Нижние оценки сложности схем из функциональных элементов (обзор) // Кибернетический сборник. Вып. 21 / ред. О. Б. Лупанов. М.: Мир, 1984. C.3-54.
Храпченко В. М. Новые соотношения между глубиной и задержкой // Дискретная математика. 1995. Т. 7. №4. C. 77-85.
Храпченко В. М. Работы Р. Г. Нигматуллина по нижним оценкам сложности // Дискретный анализ и исслед. опер. Сер. 1. 2000. Т. 7. № 1. C. 18-31.
Храпченко В. М. Квадратичная нижняя оценка сложности формул над базисом {&, Ѵ,_} для БЧХ-кодов // Математические вопросы кибернетики. Вып. 16 / ред. Н. А. Карпова. М.: Физматлит, 2007, C. 239-241.
Храпченко В. М. Об одной из возможностей уточнения оценок для задержки параллельного сумматора // Дискретный анализ и исслед. опер. Сер. 1. 2007. Т. 14. №1. C. 86-93.
Храпченко В. М. Принципиальное расхождение между глубиной и задержкой // Дискретная математика. 2008. Т. 20. №3. C. 51-72.
Храпченко В. М. Упрощенное доказательство одной нижней оценки сложности // Дискретная математика. 2013. Т. 25. №2. C. 82-84.
Храпченко В. М. Математик Олег Борисович Лупанов (1932-2006) // Чебышевский сборник. 2016. Т. 17. №2. C.6-20.
Храпченко В. М. Методы Лупанова и их значение для формирования теории синтеза схем // Чебышевский сборник. 2016. Т. 17. №2. C. 184-195.
Андреев А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности п-схем // Вестник Московского университета. Сер. 1. Математика. Механика. 1987. №1. C. 70-73.
Гашков С. Б., Гринчук М. И., Сергеев И. С. О построении схем сумматоров малой глубины // Дискретный анализ и исслед. опер. Сер. 1. 2007. Т. 14. №1. C. 27-44; 2008. Т. 15. № 4. C. 92-93.
Гринчук М. И. Уточнение верхней оценки глубины сумматора и компаратора // Дискретный анализ и исслед. опер. Сер. 1. 2008. Т. 15. № 2. C. 12-22.
Здобнов С. В. О сложности линейной функции в классе П-схем без нулевых цепей // Комбинаторно-алгебр. методы и их применение. Горький: Изд-во Горьк. ун-та, 1987. C.27-34.
Ложкин С. А., Данилов Б. Р. О задержке схем из функциональных элементов в модели с произвольным распределением задержек элементов базиса по входам и входным наборам // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 2013. №4. C. 25-33.
Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 138 c.
Нечипорук Э. И. Об одной булевской функции // Доклады АН СССР. 1966. Т. 169. №4. C. 765-767.
Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991. 240с.
Офман Ю. П. Алгоритмическая сложность дискретных функций // Доклады АН СССР. 1962. Т. 145. №1. C. 48-51.
Пулатов А. К. Нижняя оценка сложности схемной реализации для одного класса кодов // Дискретный анализ. 1974. Вып.25. C. 56-61.
Рычков К. Л. Модификация метода В. М. Храпченко и применение ее к оценкам сложности П -схем для кодовых функций // Методы дискретного анализа в теории графов и схем. Вып.42. Новосибирск: ИМ СО АН СССР, 1985. C. 91-98.
Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сибирский журнал исслед. опер. 1994. Т. 1. №4. C. 33-52.
Рычков К. Л. О нижних оценках формульной сложности линейной булевой функции // Сибирские электр. матем. известия. 2014. Т. 11. C. 165-184.
Сергеев И. С. О сложности и глубине формул для симметрических булевых функций // Вестник Московского университета. Сер. 1. Математика. Механика. 2016. №3. C. 53-57.
Субботовская Б. А. О реализации линейных функций формулами в базисе V, // Доклады АН СССР. 1961. Т. 136. №3. C. 553-555.
Угольников А. Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики // Математические заметки. 1987. Т. 42. №4. C. 603-612.
Черухин Д. Ю. Нижние оценки формульной сложности симметрических булевых функций // Дискретный анализ и исслед. опер. Сер. 1. 2000. Т. 7. №3. C. 86-98.
Черухин Д. Ю. К вопросу о логическом представлении счетчика четности // Неформальная наука. 2008. №2. C. 14-23.
Яблонский С. В. Реализация линейной функции в классе П-схем // Доклады АН СССР. 1954. Т. 94. № 5. C. 805-806.
Brent R. On the addition of binary numbers // IEEE Trans. Comp. 1970. V. C-19. No. 8. P. 758-759.
Commentz-Walter B. Size-depth tradeoff in monotone Boolean formulae // Acta Inf. 1979. V. 12. P. 227-243.
Commentz-Walter B. and Sattler J. Size-depth tradeoff in non-monotone Boolean formulae // Acta Inf. 1980. V. 14. P. 257-269.
Coppersmith D. and Schieber B. Lower bounds on the depth of monotone arithmetic computations // Proc. 33rd Symp. Foundations of Computer Sci. (Pittsburgh, 1992). Washington: IEEE CS, 1992. P.288-295.
Dunne P. E. The Complexity of Boolean Networks. San Diego: Academic Press, 1988. 512 p.
Gal A., Tal A., and Trejo Nunez A. Cubic formula size lower bounds based on compositions with majority // Electr. Colloq. Comput. Complexity. 2018. TR18-160.
Grove E. Proofs with Potential. Ph.D. thesis. Univ. of California, Berkeley, 1993.
Hastad J. The shrinkage exponent of de Morgan formulas is 2 // SIAM J. Comput. 1998. V. 27. No. 1. P. 48-64.
Held S. and Spirkl S. T. Binary adder circuits of asymptotically minimum depth, linear size, and fan-out two // ACM Trans. Algorithms. 2017. V. 14. No. 1. P. 4:1-4:18.
Hodes L. and Specker E. Length of formulas and elimination of quantifiers I // Contributions to Mathematical Logic. Amsterdam: North Holland, 1968. P. 175-188.
Jukna S. Boolean function complexity. Berlin; Heidelberg: Springer Verlag, 2012. 618 p.
Karchmer M. and Wigderson A. Monotone circuits for connectivity require super-logarithmic depth // SIAM J. Discrete Math. 1990. V.3. No.2. P.255-265.
Kosaraju S. R. Parallel evaluation of division-free arithmetic equations // Proc. 18th Symp. Theory of Comput. (Berkeley, 1986). NY: ACM, 1986. P.231-239.
Maruyama K. On the parallel evaluation of polynomials // IEEE Trans. Comp. 1973. V. C-22. No. 1. P.2-5.
McColl W. F. Some results on circuit depth. Theory of computation. Report No. 18. Coventry: Univ. of Warwick, 1977.
Munro I. and Paterson M. Optimal algorithms for parallel polynomial evaluation // J. Comp. System Sci. 1973. V. 7. P. 189-198.
Paterson M. S. An introduction to Boolean function complexity // Asterisque. 1976. V. 38-39. P.183-201.
Paterson M. S., Pippenger N., and Zwick U. Optimal carry save networks // LMS Lecture Notes Series. Boolean function complexity. V. 169 / ed. M. S. Paterson. Cambridge University Press, 1992. P. 174-201.
Paterson M. and Zwick U. Shallow circuits and concise formulae for multiple addition and multiplication // Comput. Complexity. 1993. V. 3. P. 262-291.
Preparata F. P. and Muller D. E. Efficient parallel evaluation of Boolean expressions // IEEE Trans. Comp. 1976. V. C-25. No. 5. P. 548-549.
Pudlak P. Bounds for Hodes - Specker theorem // Logic and Machines: Decision Problems and Complexity. LNCS. 1984. V. 171. P.421-445.
Ragaz M. Parallelizable algebras // Arch. Math. Logic. 1986/87. V. 26. P.77-99.
Сэвидж Дж. Э. Сложность вычислений. М.: Факториал, 1998. 368 c.
Spira P. M. On time-hardware complexity tradeoffs for Boolean functions // Proc. 4th Hawaii Symp. System Sci. N. Hollywood: Western Periodical Company, 1971. P. 525-527.
Tal A. Shrinkage of de Morgan formulae from quantum query complexity // Electr. Colloq. on Comput. Complexity. 2014. TR14-048.
Wegener I. The complexity of Boolean functions. Stuttgart: Wiley-Teubner, 1987. 470 p.
On the meaning of works by V. M. Khrapchenko | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/10