|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Верхние оценки сложности формул для симметрических булевых функцийстатья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 28 мая 2015 г.
- Автор: Сергеев И.С.
- Журнал: Известия высших учебных заведений. Математика
- Номер: 5
- Год издания: 2014
- Издательство: Изд-во Казан. ун-та
- Местоположение издательства: Казань
- Первая страница: 38
- Последняя страница: 52
- DOI: 10.3103/S1066369X14050041
- Аннотация: Показано, что сложность реализации оператора подсчета числа единиц в булевом наборе длины n формулами над базисом B2 двуместных булевых функций не превосходит n^3.03, а над стандартным базисом B0 — n^4.47. Как следствие, такие же оценки справедливы для сложности любой пороговой симметрической функции n переменных, в частности, для функции голосования. Для сложности произвольной симметрической функции n переменных получены оценки n^3.04 и n^4.48 над базисами B2 и B0 соответственно. Доказательство основано на применении модулярной арифметики.
- Добавил в систему: Сергеев Игорь Сергеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | ivm8893.pdf | 385,3 КБ | 24 июля 2015 [isserg] |