?
О нижних оценках сложности схем в базисе антицепных функций
Вестник Московского университета. Серия 1: Математика. Механика. 2013. Т. 2. С. 17-23.
Podolskaya O.
The antichain function is a characteristic function of antichain on the Boolean cube. The set of antichain functions is an infinite complete basis. We study computational complexity of Boolean functions over antichain functional basis. In this paper we prove $\sqrt{n}$ asymptotic lower bound on the computational complexity of the linear function, the majority function and almost all Boolean function of $n$ variables.
Priority areas:
mathematics
Language:
Russian
Podolskaya O., В кн. : Материалы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.). : М. : Издательство ИПМ РАН, 2013. С. 97-100.
We study Boolean circuit complexity in an infinite basis consisting of all Boolean functions that equal 1 only on sets of pair-wise incomparable tuples. It is known that lower bounds on the complexity of linear function, majority function and almost all boolean functions of $n$ variables are of the order $\sqrt n.$ We show that ...
Added: May 31, 2015
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2014 Т. 3 № 31 С. 78-100
Background
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
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
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58-77
Background
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
Danilov B. R., Ложкин С. А., Прикладная математика и информатика 2018 № 59 С. 40-49
В работе предлагается метод синтеза усилительных схем из функциональных элементов (УСФЭ), позволяющий установить асимптотику функции Шеннона для обобщённой глубины УСФЭ – то есть глубины самой «плохой» функции алгебры логики, зависящей от заданных переменных – в специальном базисе (модели глубины), где глубина элемента определяется как его типом, так и степенью ветвления выхода в схеме. Асимптотическое поведение ...
Added: December 2, 2019
Lozhkin S. A., Shupletsov M. S., Danilov B.R., Математические вопросы криптографии 2017 Vol. 8 No. 2 P. 87-96
We propose several asymptotically size-optimal Boolean circuits synthesis methods that implement arbitrary Boolean functions of a given number of Boolean variables with a given protection level from functionality inference when concealing some number of local interconnections. These methods rely on the structure of Boolean circuits over arbitrary finite complete basis. Constructed by methods of generalized ...
Added: December 1, 2019
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
Podolskaya O., В кн. : Материалы X молодежной научной школы по дискретной математике и ее приложениям. : М. : Издательство ИПМ РАН, 2015. С. 56-58.
Доказано, что сложность реализации произвольной симметрической булевой функции f от n переменных для f не равной тождественно единице при реализации схемами в базисе антицепных функций, т.е. функций, принимающих значение 1 лишь на попарно несравнимых наборах, равна min(k(f),n-k(f)+2), где k(f) - количество слоев, на которых функция f равна 1. ...
Added: January 11, 2016
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
Podolskaya O., Вестник Московского университета. Серия 1: Математика. Механика 2016 № 2 С. 51-52
Изучается сложность реализации булевых функций схемами из функциональных элементов в базисе, состоящем из всех характеристических функций антицепей булева куба. Установлено, что сложность реализации функции четности от $n$ переменных есть $\lfloor \frac{n+1}{2} \rfloor,$ сложность ее отрицания равна сложности функции голосования от $n$ переменных и составляет $\lceil \frac{n+1}{2} \rceil$. ...
Added: March 14, 2017
Ilyashenko Y., Яковенко С. Ю., М. : МЦНМО, 2013
Предлагаемая книга—первый том двухтомной монографии, посвящённой аналитической теории дифференциальных уравнений.
В первой части этого тома излагается формальная и аналитическая теория нормальных форм и теорема о разрешении особенностей для векторных полей на плоскости.
Вторая часть посвящена алгебраически разрешимым локальным задачам теории аналитических дифференциальных уравнений , квадратичным векторным полям и проблеме локальной классификации ростков векторных полей в комплексной области ...
Added: February 5, 2014
Kalyagin V.A., Koldanov A.P., Koldanov P.A. et al., Physica A: Statistical Mechanics and its Applications 2014 Vol. 413 No. 1 P. 59-70
A general approach to measure statistical uncertainty of different filtration techniques for market network analysis is proposed. Two measures of statistical uncertainty are introduced and discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases ...
Added: July 19, 2014
Losev A. S., Slizovskiy S., JETP Letters 2010 Vol. 91 P. 620-624
Added: February 27, 2013
191574970, Functional Analysis and Its Applications 2006 Vol. 40 No. 2 P. 81-90
It is well known that every module M over the algebra ℒ(X) of operators on a finite-dimensional space X can be represented as the tensor product of X by some vector space E, M ≅ = E ⊗ X. We generalize this assertion to the case of topological modules by proving that if X is a stereotype space with the stereotype approximation property, then for each stereotype module M over the ...
Added: September 23, 2016
Maslov V., Теоретическая и математическая физика 2019 Т. 201 № 1 С. 65-83
We study the process of a nucleon separating from an atomic nucleus from the mathematical standpoint
using experimental values of the binding energy for the nucleus of the given substance. A nucleon becomes
a boson at the instant of separating from a fermionic nucleus. We study the further transformations of
boson and fermion states of separation in a ...
Added: November 1, 2019
Pahomov F., Известия РАН. Серия математическая 2016 Т. 80 № 6 С. 173-216
Полимодальная логика доказуемости
GLP была введена Г. К. Джапаридзе в 1986 г. Она является логикой доказуемости для ряда цепочек предикатов доказуемости возрастающей силы. Всякой полимодальной логике соответствует многообразие полимодальных алгебр. Л. Д. Беклемишевым и А. Виссером был поставлен вопрос о разрешимости элементарной теории свободной GLP-алгебры, порожденной константами 0, 1 [1]. В этой статье для любого натурального n решается аналогичный вопрос для логик GLPn, являющихся ...
Added: December 4, 2017
Sinelshchikov D., Кудряшов Н. А., Theoretical and Mathematical Physics 2018 Vol. 196 No. 2 P. 1230-1240
We study a family of nonautonomous generalized Liénard-type equations. We consider the equivalence problem via the generalized Sundman transformations between this family of equations and type-I Painlevé–Gambier equations. As a result, we find four criteria of equivalence, which give four integrable families of Liénard-type equations. We demonstrate that these criteria can be used to construct ...
Added: February 9, 2019
ООО Фирма "Элист", 2014
В книге представлены тезисы докладов I тура XV Всероссийской научно-технической конференции и школы молодых ученых, аспирантов и студентов. ...
Added: October 17, 2014
Vyalyi M., Дискретная математика 1991 Т. 3 № 3 С. 35-45
Added: October 17, 2014
Levashov M., Кухаренко А. В., Вопросы защиты информации 2018 № 2 С. 66-71
Рассматривается статистическая модель одного этапа системы фрод-мониторинга транзакций в интернет-банкинге. Построен и рассчитан близкий к отношению правдоподобия критерий отсева мошеннических транзакций. Для выборочных распределений, полученных на выборке объема в 1 млн реальных транзакций, вычислены параметры эффективности этого критерия. ...
Added: June 14, 2018
Kolokolov I., Lebedev V., Sizov G. A., Journal of Experimental and Theoretical Physics 2011 Vol. 140 No. 2 P. 387-400
We analyze magnetic kinematic dynamo in a conducting fluid where the stationary shear flow is accompanied by relatively weak random velocity fluctuations. The diffusionless and diffusion regimes are described. The growth rates of the magnetic field moments are related to the statistical characteristics of the flow describing divergence of the Lagrangian trajectories. The magnetic field ...
Added: February 2, 2017
Kotelnikova M. V., Aistov A., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189
The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...
Added: January 28, 2020
Min Namkung, Younghun K., Scientific Reports 2018 Vol. 8 No. 1 P. 16915-1-16915-18
Sequential state discrimination is a strategy for quantum state discrimination of a sender’s quantum
states when N receivers are separately located. In this report, we propose optical designs that can
perform sequential state discrimination of two coherent states. For this purpose, we consider not
only binary phase-shifting-key (BPSK) signals but also general coherent states, with arbitrary prior
probabilities. Since ...
Added: November 16, 2020
Zinder Y., Lazarev A. A., Musatova E. G., Автоматика и телемеханика 2020 Т. 5 С. 91-104
Представлен полиномиальный алгоритм корректировки расписания движения поездов для случая, когда один из путей двухпутной железной дороги становится недоступным, оставшийся путь содержит разъезд, а все поезда делятся на две категории: приоритетные поезда, например пассажирские, и обычные поезда, к которым относятся большинство грузовых поездов. Представленный алгоритм минимизирует негативное влияние, оказываемое блокировкой пути, сначала для приоритетных поездов, а ...
Added: September 2, 2020