Уклоняющаяся булева функция

В математике уклоняющаяся булева функция $f$ (из $n$ переменные) — это булева функция , для которой каждый алгоритм дерева решений имеет время работы ровно $n$. Следовательно, каждый алгоритм дерева решений , представляющий функцию, в худшем случае имеет время работы $n$.

Определение

Тип алгоритмов, рассматриваемых при определении уклоняющейся булевой функции, представляет собой деревья решений , в которых каждый внутренний узел проверяет значение одной из заданных логических переменных и соответственно разветвляется. Каждый листовой узел дерева определяет значение функции для входных данных, достигающих этого узла. наихудшего случая Сложность дерева решений для данного дерева решений - это количество переменных, проверенных на самом длинном пути от корня к листу дерева. Каждый $n$Функция -переменная имеет алгоритм дерева решений, который точно проверяет $n$ переменные на всех входах, используя дерево решений, в котором все узлы на уровне $i$ протестировать $i$-я переменная. Функция является уклончивой, если никакое другое дерево решений для той же функции не имеет меньшей сложности. Для уклоняющейся функции любое дерево решений должно иметь хотя бы один вход, ведущий к пути в дереве, по которому проверяются все входные переменные.

Примеры

Построить неуклоняющиеся функции тривиально, построив деревья решений, в которых каждая ветвь завершается перед проверкой всех переменных. Например, функция «всегда истина» имеет дерево решений без тестов. В качестве менее тривиального примера, в котором все переменные используются для определения значения функции, рассмотрим функцию трех переменных. $x$, $y$, и $z$ который возвращает либо $y$ или $z$ в зависимости от того, $x$ истинно или ложно соответственно. У него есть дерево решений, которое сначала проверяет $x$, а затем проверяет только один из $y$ или $z$ на каждой ветке.

Если ветвь дерева решений завершается до проверки всех переменных, то она дает значение функции для четного числа комбинаций аргументов: $2^{n-t}$ комбинации, где $n$ количество переменных и $t$ это число, протестированное на этой ветке. Следовательно, если булева функция имеет нечетное количество комбинаций аргументов, для которых она истинна, то она должна быть уклончивой. Например, логические и логические функции или верны для 1 и $2^{n}-1$ комбинации аргументов соответственно, оба из которых являются нечетными числами (для $n>0$), поэтому они уклончивы.

История

Понятие уклоняющей функции было введено в связи с исследованием графовых алгоритмов для графов, определенных в неявной графовой модели, где алгоритм имеет доступ к графу только через подпрограмму проверки смежности вершин. В этом приложении свойство графа можно описать как булеву функцию, входные переменные которой истинны, если между двумя вершинами присутствует ребро, а свойство является уклончивым, если каждый алгоритм должен (на некоторых входных данных) проверять существование каждого потенциального ребра. Ранние работы в этой области доказали, что постоянная доля ребер должна быть проверена на наличие любого нетривиального свойства монотонного графа; здесь «нетривиальный» означает, что функция имеет более одного значения, а «монотонный» означает, что добавление ребер в граф не может изменить значение функции с истинного на ложное. Эти частичные результаты послужили мотивом для формулировки до сих пор недоказанной гипотезы Андераа-Карпа-Розенберга , согласно которой все нетривиальные свойства монотонного графа уклончивы.

Гипотеза Андераа-Карпа-Розенберга вытекает из более общей гипотезы об уклончивости булевых функций: каждая нетривиальная монотонная булева функция, имеющая симметрии, переводящие любую переменную в любую другую переменную, является уклончивой. Эта гипотеза также остается недоказанной, но известно, что она верна для определенных значений $n$, включая высшие державы . Это было названо гипотезой уклончивости .