RUS
ENG
Полная версия
ЖУРНАЛЫ
// Вестник Московского университета. Серия 1: Математика. Механика
// Архив
Вестн. Моск. ун-та. Сер. 1. Матем., мех.,
2017
,
номер 5,
страницы
51–55
(Mi vmumm96)
Краткие сообщения
Несравнимые интервалы и приближенное вычисление монотонных булевых функций
А. В. Чашкин
Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Оценивается число несравнимых
$k$
-мерных интервалов в
$n$
-мерном булевом кубе. Полученный результат используется для оценки сложности приближенного вычисления произвольной
$n$
-местной монотонной булевой функции.
Ключевые слова:
монотонная булева функция, сложность приближенного вычисления, несравнимые интервалы.
УДК:
519.7
Поступила в редакцию:
12.10.2016
Полный текст:
PDF файл (312 kB)
Список литературы
Англоязычная версия:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2017,
72
:5,
206–209
Реферативные базы данных:
©
МИАН
, 2024