Аннотация:
Рассматривается класс булевых функций $F_{n,k}$, состоящий из всех тех функций от $n$ переменных, каждая из которых обращается в единицу ровно на $k$ наборах значений переменных. Для функций из $F_{n,k}$ получены линейные по $n$ оценки сложности реализации схемами из функциональных элементов над базисом, содержащим все булевы функции от двух переменных, кроме двух линейных функций, $x\oplus y$ и
$x\oplus y\oplus1$. Из этих оценок следует, что при небольших значениях $k$, например, при $k<\ln n$, известный метод Финикова позволяет строить асимптотически минимальные схемы для всех функций из $F_{n,k}$. В некоторых случаях полученные нижние оценки сложности схем позволяют доказывать минимальность рассматриваемых схем.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 02–01–00985, грантом НШ-1807.2003.1 программы Президента Российской
Федерации поддержки ведущих научных школ и программой «Университеты России».
Образец цитирования:
Н. П. Редькин, “О сложности булевых функций с малым числом единиц”, Дискрет. матем., 16:4 (2004), 20–31; Discrete Math. Appl., 14:6 (2004), 619–630
\RBibitem{Red04}
\by Н.~П.~Редькин
\paper О сложности булевых функций с~малым числом единиц
\jour Дискрет. матем.
\yr 2004
\vol 16
\issue 4
\pages 20--31
\mathnet{http://mi.mathnet.ru/dm172}
\crossref{https://doi.org/10.4213/dm172}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2141142}
\zmath{https://zbmath.org/?q=an:1104.94068}
\transl
\jour Discrete Math. Appl.
\yr 2004
\vol 14
\issue 6
\pages 619--630
\crossref{https://doi.org/10.1515/1569392043272511}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm172
https://doi.org/10.4213/dm172
https://www.mathnet.ru/rus/dm/v16/i4/p20
Эта публикация цитируется в следующих 6 статьяx:
Н. П. Редькин, “Об асимптотиках для сложности булевых функций
с малым числом единиц”, Матем. заметки, 109:2 (2021), 257–263; N. P. Red'kin, “Asymptotics for the Complexity of Boolean Functions with Small Number of Ones”, Math. Notes, 109:2 (2021), 256–261
Н. П. Редькин, “О сложности реализации булевых функций с малым числом единиц”, Дискрет. матем., 32:2 (2020), 32–43; N. P. Red'kin, “Implementation complexity of Boolean functions with a small number of ones”, Discrete Math. Appl., 31:4 (2021), 271–279
Редькин Н.П., “О сложности реализации булевых функций с малым числом единиц самокорректирующимися контактными схемами”, Вестник Московского университета. Серия 1: Математика. Механика, 2011, № 1, 19–21
Н. П. Редькин, “О сложности реализации булевых функций с малым числом единиц самокорректирующимися контактными схемами”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2011, № 1, 19–21; N. P. Red'kin, “On the complexity of the realization of Boolean functions with a small number of ones by self-correcting switching circuits”, Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 66:1 (2011), 17–19
Н. П. Редькин, “Об оценках сложности схем из многовходовых функциональных элементов”, Дискрет. матем., 22:1 (2010), 50–57; N. P. Redkin, “On bounds for complexity of circuits of multi-input functional elements”, Discrete Math. Appl., 20:1 (2010), 85–93
Stasys Jukna, “Disproving the Single Level Conjecture”, SIAM J. Comput., 36:1 (2006), 83
Цитирование в формате AMSBIB
Обратная связь: