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

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

Авторы

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

Тэги

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

Тематические рубрики

Прикладные науки. Медицина. Технология

Предметные рубрики

Физико-математические науки

В этом же номере:

Моделирование напряженно-деформированного состояния и оценка несущей способности лопаток при испытаниях корпусов на непробиваемость, Об одной форме упругого потенциала для высокоэластичного материала, ...

Резюме по документу**

Антицепной функцией называется характеристическая функция антицепи в булевом кубе. <...> Множество всех антицепных функций образует бесконечный полный базис. <...> В работе изучается сложность реализации булевых функций схемами в этом базисе. <...> Доказаны нижние оценки порядка корень из n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных. <...> Антицепной функцией называется характеристическая функция антицепи в булевом кубе. <...> Множество всех антицепных функций образует бесконечный полный базис. <...> В работе изучается сложность реализации булевых функций схемами в этом базисе. <...> Доказаны нижние оценки порядка корень из n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных. <...>

** - вычисляется автоматически, возможны погрешности

Похожие документы:

Похожие документы из РУАЭСТ
|
Похожие документы из Руконт

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

Помощь:

Участники: