RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, номер 2, страницы 17–23 (Mi vmumm388)

Эта публикация цитируется в 3 статьях

Математика

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

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

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

Ключевые слова: антицепная функция, булевы схемы, линейная функция, функция голосования.

УДК: 519.6

Поступила в редакцию: 15.06.2012


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2013, 68:2, 98–103

Реферативные базы данных:


© МИАН, 2024