Vyhýbavá logická funkce - Evasive Boolean function

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Evasive Boolean function"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Listopadu 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, an vyhýbací booleovská funkce ƒ (z n proměnné) je a Booleovská funkce pro které každý algoritmus rozhodovacího stromu má provozní dobu přesněn. V důsledku toho každý algoritmus rozhodovacího stromu který představuje funkci, v nejhorším případě dobu běhun.

Příklady

Příklad pro nevyhýbající se booleovskou funkci

Následuje booleovská funkce pro tři proměnné X, y, z:

${ displaystyle ~ f (x, y, z) ~}$	${ displaystyle ~ = ~}$	${ displaystyle ~ (x land y) ~}$	${ displaystyle ~ lor ~}$	${ displaystyle ~ ( neg x land z) ~}$
	${ displaystyle ~ = ~}$		${ displaystyle ~ lor ~}$

(kde ${ displaystyle land}$ je bitový "a", ${ displaystyle lor}$ je bitové "nebo" a ${ displaystyle neg}$ je bitové „ne“).

Tato funkce není úhybná, protože existuje rozhodovací strom, který ji řeší kontrolou přesně dvou proměnných: Algoritmus nejprve zkontroluje hodnotuX. Li X je pravda, algoritmus kontroluje hodnotu y a vrátí ji.

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

Li X je false, algoritmus kontroluje hodnotu z a vrátí ji.

Jednoduchý příklad pro úhybnou booleovskou funkci

Zvažte tuto jednoduchou funkci „a“ na třech proměnných:

${ displaystyle ~ f (x, y, z) ~}$	${ displaystyle ~ = (x klín y klín z) ~}$

Vstup pro nejhorší případ (pro každý algoritmus) je 1, 1, 1. V každém pořadí, které se rozhodneme zkontrolovat proměnné, musíme zkontrolovat všechny. (Všimněte si, že obecně může existovat jiný vstup v nejhorším případě pro každý algoritmus rozhodovacího stromu.) Proto funkce: "a", "nebo" (na n proměnné) jsou úhybné.

Binární hry s nulovým součtem

Pro případ binárních hry s nulovým součtem, každý vyhodnocovací funkce je vyhýbavý.

V každé hře s nulovým součtem je hodnoty hry dosaženo pomocí minimax algoritmus (hráč 1 se snaží maximalizovat zisk a hráč 2 se snaží minimalizovat náklady).

V binárním případě se funkce max rovná bitovému "nebo" a funkce min se rovná bitovému "a".

Rozhodovací strom pro tuto hru bude mít tuto formu:

• každý list bude mít hodnotu v {0, 1}.
• každý uzel je připojen k jednomu z {"a", "nebo"}

Pro každý takový strom s n listy, v nejhorším případě je doba chodu n (což znamená, že algoritmus musí zkontrolovat všechny listy):

Vystavíme protivník který produkuje vstup v nejhorším případě - pro každý list, který algoritmus kontroluje, protivník odpoví 0, pokud je rodičem listu uzel Or, a 1, pokud je rodič uzlem And.

Tento vstup (0 pro všechny podřízené uzly Or a 1 pro všechny podřízené uzly And) vynutí, aby algoritmus zkontroloval všechny uzly:

Stejně jako v druhém příkladu

• za účelem výpočtu Nebo Výsledkem je, že pokud jsou všechny děti 0, musíme je všechny zkontrolovat.
• Za účelem výpočtu A Výsledkem je, že pokud jsou všechny děti 1, musíme je všechny zkontrolovat.

Viz také

• Aanderaa – Karp – Rosenbergova domněnka, domněnka, že každá netriviální monotónní vlastnost grafu je úhybná.