Уклоняющаяся логическая функция - Evasive Boolean function

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

Примеры

Пример не уклоняющейся логической функции

Ниже приводится логическая функция от трех переменных. Икс, у, z:

${ Displaystyle ~ е (х, у, г) ~}$	${ Displaystyle ~ = ~}$	${ Displaystyle ~ (х земля у) ~}$	${ displaystyle ~ lor ~}$	${ Displaystyle ~ ( отр х земля г) ~}$
	${ Displaystyle ~ = ~}$		${ displaystyle ~ lor ~}$

(куда ${ displaystyle land}$ это побитовое "и", ${ displaystyle lor}$ это побитовое "или", и ${ displaystyle neg}$ это побитовое «не»).

Эта функция не является уклончивой, потому что существует дерево решений, которое решает ее, проверяя ровно две переменные: алгоритм сначала проверяет значениеИкс. Если Икс верно, алгоритм проверяет значение у и возвращает его.

(

{ displaystyle ( neg x = { text {false}}) ~~ Rightarrow ~~ (( neg x land z) = { text {false}})}

)

Если Икс ложно, алгоритм проверяет значение z и возвращает его.

Простой пример уклончивой логической функции

Рассмотрим эту простую функцию «и» от трех переменных:

${ Displaystyle ~ е (х, у, г) ~}$	${ Displaystyle ~ = (х клин у клин г) ~}$

В худшем случае входные данные (для каждого алгоритма) - 1, 1, 1. В каждом порядке, в котором мы выбираем проверку переменных, мы должны проверять их все. (Обратите внимание, что в общем случае для каждого алгоритма дерева решений могут быть разные входные данные для наихудшего случая.) Следовательно, функции: «и», «или» (на п переменные) уклончивы.

Бинарные игры с нулевой суммой

В случае двоичного игры с нулевой суммой, каждый функция оценки уклончиво.

В каждой игре с нулевой суммой ценность игры достигается за счет минимакс алгоритм (игрок 1 пытается максимизировать прибыль, а игрок 2 пытается минимизировать затраты).

В двоичном случае функция max равняется поразрядному «или», а функция min равна поразрядному «и».

Дерево решений для этой игры будет иметь следующий вид:

каждый лист будет иметь значение в {0, 1}.
каждый узел подключен к одному из {"и", "или"}

Для каждого такого дерева с п уходит, время работы в худшем случае составляет п (это означает, что алгоритм должен проверить все листья):

Мы покажем противник который производит входные данные в наихудшем случае - для каждого листа, который проверяет алгоритм, злоумышленник ответит 0, если родительский элемент является узлом Or, и 1, если родительский узел является узлом And.

Этот ввод (0 для всех дочерних узлов Or и 1 для всех дочерних узлов And) заставляет алгоритм проверять все узлы:

Как и во втором примере

для расчета Или же результат, если все дети равны 0, мы должны проверить их всех.
Чтобы рассчитать И результат, если все дети 1, мы должны проверить их всех.

Смотрите также

Гипотеза Андераа – Карпа – Розенберга, гипотеза о том, что любое нетривиальное свойство монотонного графа уклоняется.