О сложности монотонных схем для пороговых симметрических булевых функций

Сергеев, И.С.

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 29 июля 2020 г.

Автор: Сергеев И.С.
Журнал: Дискретная математика
Том: 32
Номер: 1
Год издания: 2020
Издательство: ФГБУ "Издательство "Наука"
Местоположение издательства: Москва
Первая страница: 81
Последняя страница: 109
DOI: 10.4213/dm1547
Аннотация: Показано, что сложность реализации монотонной симметрической булевой функции n переменных с порогом k=O(1) схемами над базисом {∨,∧} не превосходит 2(log k)n+o(n). Кроме того, доказано, что сложность функции с порогом 2 равна 2n+Θ(\sqrt n), а сложность функции с порогом 3 равна 3n+O(log n) — установлены соответствующие нижние оценки.
Добавил в систему: Сергеев Игорь Сергеевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

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

Прикрепленные файлы