?
Сравнение оценок сложности для задач Р. Беллмана и О. Б. Лупанова
С. 4–16.
Kochergin V.
In book
М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022.
V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594
The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. ...
Added: February 28, 2026
Kochergin V., Mikhailovich A., Математические заметки 2025 Т. 117 № 4 С. 523–542
The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. ...
Added: April 8, 2025
Mikhailovich A., Kochergin V., М.: Физматлит, 2024.
Added: March 10, 2025
Golota A., Известия РАН. Серия математическая 2024 Т. 88 № 5 С. 47–66
Let X be a complex projective variety. Suppose that the group of birational automorphisms of X contains finite subgroups isomorphic to (Z/NZ)^r for r fixed and N arbitrarily large. We show that r does not exceed 2dim(X). Moreover, the equality holds if and only if X is birational to an abelian variety. We also show that an analogous ...
Added: November 6, 2024
Kochergin V., Mikhailovich A., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803
The problem of determining the nonmonotone complexity of the implementation ofk-valued logic functions by logic circuits in bases consisting of all monotone (with respect to thestandard order) functions and finitely many nonmonotone functions is investigated. In calculatingthe complexity measure under examination only those elements of the circuit which are assignednonmonotone basis functions are taken into ...
Added: November 19, 2023
Kochergin V., Mikhailovich A., В кн.: Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.).: М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 76–79.
Установлена нижняя оценка немонотонной сложности функций многозначной логики, отличающающаяся от известной верхней оценки не более чем на абсолютную константу ...
Added: October 29, 2022
Kochergin V., Чебышевский сборник 2022 Т. 23 № 2(83) С. 121–150
В работе предпринята попытка не только дать обзор результатов, полученных
О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем,
проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций ...
Added: October 29, 2022
Mikhailovich A., Kochergin V., В кн.: Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова.: Изд-во механико-математического факультета МГУ, 2019. С. 129–131.
Added: December 7, 2021
Kochergin V., Mikhailovich A., В кн.: Проблемы теоретической кибернетики. Материалы заочного семинара XIX международной конференции.: Издательство Казанского (Приволжского) федерального университета, 2021. С. 75–78.
В работе исследуется сложность реализации функций многозначной логики над базисами, содержащими все монотонные функции и конечное число немонотонных функций. Получены верхняя и нижняя оценка, отличающиеся на константу, не зависящую от базиса. ...
Added: December 6, 2021
Kochergin V., Mikhailovich A., Ученые записки Казанского университета. Серия: Физико-математические науки 2020 Т. 162 № 3 С. 311–321
The problem of the complexity of multi-valued logic functions realization by circuits
in a special basis is investigated. This kind of basis consists of elements of
two types. The first type of elements are monotone functions with zero weight.
The second type of elements are non-monotone elements with unit weight.
The non-empty set of elements of this type is ...
Added: December 6, 2021
V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28–35
We study the complexity of the realization of Boolean functions by circuits in infinite complete bases containing all monotone functions with zero weight (cost of use) and finitely many nonmonotone functions with unit weight. The complexity of the realization of Boolean functions in the case where the only nonmonotone element of the basis is negation ...
Added: April 22, 2019
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13–25
We investigate the realization complexity of k-valued logic functions k ≥ 2 by combinational circuits in an infinite basis that includes the negation of the Lukasiewicz function, i.e., the function k−1−x, and all monotone functions. Complexity is understood as the total number of circuit elements. For an arbitrary function f, we establish lower and upper ...
Added: April 22, 2019
Kochergin Vadim V., Mikhailovich Anna V., Discrete Mathematics and Applications 2017 Vol. 27 No. 5 P. 295–302
The paper is concerned with the complexity of realization of 𝑘-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be 0. The complexity problem of realizations of Boolean functions over a basis having negation as the only ...
Added: March 14, 2018
Mikhailovich A., Kochergin V., Математические заметки 2019 Т. 105 № 1 С. 32–41
A problem of complexity of Boolean functions realization over infinite complete bases of special type is studied. These bases contain all monotone functions with zero weight and finite number of non-monotone functions with unit weight. Exhaustive description of Boolean realization over basis that consists of all monotone functions and one non-monotone function negation has been ...
Added: September 28, 2017
Mikhailovich A.V., Kochergin V.V., Siberian Electronic Mathematical Reports 2017 Vol. 14 P. 1100–1107
The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements ...
Added: September 28, 2017
Kochergin V., Mikhailovich A., Дискретный анализ и исследование операций 2018 Т. 25 № 1 С. 42–74
The complexity of realization of k-valued logic functions by circuits in a special infinite basis is invesigated. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. The upper and the lower bounds of the complexity were ...
Added: September 28, 2017
Mikhailovich A., Kochergin V., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105
The problem of the effective realization of Boolean functions and multi-valued logic functions by circuits in some infinite bases is considered. The bases consist of all monotone functions and finite number of non-monotone functions. The measure of the realization efficiency is non-monotone complexity. That is the number of non-monotone elements in the circuit (we assume ...
Added: September 28, 2017
Mikhailovich A., Kochergin V., В кн.: Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем".: Улан-Удэ: Издательство Бурятского госуниверситета, 2017. С. 48–52.
Problem of multi-valued function realization by logic circuits in special bases is investigated. These bases consist of all monotone functions with zero weight and finite number of non-monotone functions with unit weight. ...
Added: September 22, 2017
Михайлович А. В., Кочергин В. В., В кн.: Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.).: М.: МАКС Пресс, 2017. С. 142–144.
The problem of multi-valued functions realization by circuits over special basis is inverstigated. The basis consis of Post negation and all monotone functions. ...
Added: September 21, 2017
Mikhailovich A., Kochergin V., Дискретная математика 2016 Т. 28 № 4 С. 80–90
In this paper we consider the complexity of realization of k-valued logic functions by logic circuits over an infinite complete basis of special type. This basis contain all monotone functions with zero weight and non-monotone functions with non-zero weight. The problem of the complexity of a Boolean functions realization over basis containing all monotone functions ...
Added: February 25, 2017
Mikhailovich A., Kochergin V., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 142–145.
Different generalizations of Markov's theorem conserning inversion complexity of Boolean functions systems are considered. ...
Added: August 31, 2016
Kochergin V., Mikhailovich A., Прикладная дискретная математика 2015 № 4 С. 24–31
Complexity of realization of Boolean functions and Boolean function systems over a basis which consist of all monotone functions and finite number of non-monotone funcitons is investigated. The weight of any monotone function from the basis equal 0. The weight of non-monotone function is positive. A. A. Markov studied special case of such basis. The ...
Added: December 8, 2015
Hirsch E., Melanich O., Nikolenko S. I., Journal of Mathematical Sciences 2012 Vol. 399 P. 32–64
In 1992, A. Hiltgen provided first constructions of provably (slightly) secure cryptographic primitives, namely feebly one-way functions. These functions are provably harder to invert than to compute, but the complexity (viewed as the circuit complexity over circuits with arbitrary binary gates) is amplified only by a constant factor (in Hiltgen’s works, the factor approaches 2). ...
Added: February 19, 2013