Об оценках функций Шеннона сложности схем в некоторых бесконечных базисах

О. В. Подольская

?

Об оценках функций Шеннона сложности схем в некоторых бесконечных базисах

С. 150–152.

Подольская О. В.

В работе изучается сложность реализации булевых функций схемами из функциональных элементов в двух бесконечных полных базисах. Первый базис состоит из линейных и антицепных функций от любого числа переменных. В этом базисе установлена верхняя оценка сложности реализации произвольной булевой функции от n переменных порядка (logn)*n^{1/2}. Также в этом базисе доказана нижняя оценка порядка n^{1/2} наибольшей сложности булевых функций от n переменных. Второй базис состоит из функций голосования и антицепных функций от любого числа переменных. Доказано, что в этом базисе наибольшая сложность булевых функций от n переменных по порядку роста равна logn.

Язык: русский

Ключевые слова: сложность булевых функций

В книге

Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.)

М.: Изд-во механико-математического факультета МГУ, 2016.

Немонотонная сложность как обобщение инверсионной сложности

Михайлович А. В., Кочергин В. В., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105

Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только ...

Добавлено: 28 сентября 2017 г.

Сложность линейных функций и функции голосования в базисе антицепных функций

Подольская О. В., Вестник Московского университета. Серия 1: Математика. Механика 2016 № 2 С. 51–52

Изучается сложность реализации булевых функций схемами из функциональных элементов в базисе, состоящем из всех характеристических функций антицепей булева куба. Установлено, что сложность реализации функции четности от $n$ переменных есть $\lfloor \frac{n+1}{2} \rfloor,$ сложность ее отрицания равна сложности функции голосования от $n$ переменных и составляет $\lceil \frac{n+1}{2} \rceil$. ...

Добавлено: 14 марта 2017 г.

Сложность реализации симметрических булевых функций схемами в базисе антицепных функций

Подольская О. В., Дискретная математика 2015 Т. 27 № 3 С. 95–107

Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе, состоящем из всех характеристических функций антицепей на булевом кубе. Установлено точное значение сложности реализации произвольной симметрической функции схемами в этом базисе. В частности, для функций четности и голосования от $n$ переменных при всех натуральных $n\geq1$ получены точные значения сложности: $\lfloor \frac{n+1}{2} \rfloor$ и ...

Добавлено: 14 марта 2017 г.

О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами

Кочергин В. В., Михайлович А. В., Прикладная дискретная математика 2015 № 4 С. 24–31

Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. ...

Добавлено: 8 декабря 2015 г.

Some Extension of Inversion Complexity of Boolean Functions

A.V. Mikhailovich, V. V. Kochergin, / Series math "arxiv.org". 2015.

Добавлено: 15 июня 2015 г.