Главная
страница
Исследования Средняя сложность булевых функций(the average
complexity of Boolean functions)
является одной из фундаментальных мер сложности
вычислительных алгоритмов.
Во многих ситуациях именно среднее по всем возможным значениям аргументов число шагов является наиболее
реалистичной мерой сложности.
На данной странице сайта рассматриваются неветвящиеся вычисления
булевых функций и изучается их средняя сложность.
Проблема сравнения булевых базисов
состоит в следующем: во сколько раз может отличатся сложность реализации булевой функции формулами
в разных базисах.
Будет ли это отношение ограничено сверху некоторой константой, зависящей от пары базисов,
или же будет неограниченным?
