Статья в сборнике "Математические вопросы кибернетики" №20, Москва, 2022
Авторы:Чашкин А.В.
Асимптотические оценки средней сложности булевых функций
Аннотация:
В работе рассматриваются некоторые из полученных в последние годы результатов, связанных со средней сложностью вычисления булевых функций неветвящимися программами с условной остановкой. Эти программы обобщают понятие схемы из функциональных элементов и являются естественной моделью неветвящихся вычислений - вычислений, в которых нет условного перехода и косвенной адресации, но есть возможность досрочного прекращения работы при выполнении определенного условия. Такие вычисления неформально можно представить следующим образом. Вычисления выполняет процессор, снабженный памятью, состоящей из отдельных ячеек. Процессор способен вычислять некоторое количество элементарных функций, составляющих базис вычисления. Каждая ячейка памяти в любой момент времени доступна процессору как для чтения, так и для записи информации. Процессор работает под управление программы, являющейся последовательностью элементарных команд двух видов. Каждая команда первого вида вычисляет значение некоторой базисной функции, аргументами которой является содержимое определенных ячеек памяти. Вычисленный результат также помещается в одну из ячеек памяти. Команда второго вида может прекратить выполнение программы. Каждая такая команда имеет единственный аргумент - содержимое некоторой ячейки памяти. Если значение аргумента равно определенному фиксированному числу, например единице, то процессор прекращает работу. Если значение аргумента иное, то выполняется следующая команда программы. В памяти выделяется ряд специальных ячеек, содержимое которых после прекращения работы объявляется результатом работы программы. Естественной мерой сложности таких программ является среднее по всем возможным аргументам время работы.
Ключевые слова:
Булева функция, средняя сложность асимптотические оценки