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

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2017, номер 5, страницы 51–55 (Mi vmumm96)

Краткие сообщения

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

А. В. Чашкин

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

Аннотация: Оценивается число несравнимых $k$-мерных интервалов в $n$-мерном булевом кубе. Полученный результат используется для оценки сложности приближенного вычисления произвольной $n$-местной монотонной булевой функции.

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

УДК: 519.7

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


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2017, 72:5, 206–209

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


© МИАН, 2024