Unikalna funkcja boolowska

W matematyce wymijająca funkcja Boole'a ƒ (z n zmiennych) jest funkcją Boole'a , dla której każdy algorytm drzewa decyzyjnego ma czas działania dokładnie n . W konsekwencji każdy algorytm drzewa decyzyjnego reprezentujący funkcję ma w najgorszym przypadku czas działania n .

Przykłady

Przykład niewymijającej funkcji boolowskiej

Poniżej przedstawiono funkcję logiczną dla trzech zmiennych x , y , z :

${\ Displaystyle ~ f (x, y, z) ~}$	${\ Displaystyle ~ = ~}$	${\ Displaystyle ~ (x \ ziemia y) ~}$	${\ displaystyle ~ \ lor ~}$	${\ Displaystyle ~ (\ neg x \ ziemia z) ~}$
	${\ Displaystyle ~ = ~}$		${\ displaystyle ~ \ lor ~}$

(gdzie $bitowe$ „i”, to bitowe „lub”, a $)$ bitowe „nie $.$

Ta funkcja nie jest wymijająca, ponieważ istnieje drzewo decyzyjne, które rozwiązuje ją, sprawdzając dokładnie dwie zmienne: Algorytm najpierw sprawdza wartość x . Jeśli x jest prawdziwe, algorytm sprawdza wartość y i zwraca ją.

( ${\ Displaystyle (\ neg x = {\ tekst {fałsz}}) ~~ \ Strzałka w prawo ~ ~ ((\ neg x \ ziemia z) = {\text{fałsz}})}$ )

Jeśli x jest fałszywe, algorytm sprawdza wartość z i zwraca ją.

Prosty przykład wymijającej funkcji boolowskiej

Rozważ tę prostą funkcję „i” dla trzech zmiennych:

${\ Displaystyle ~ f (x, y, z) ~}$	${\ Displaystyle ~ = (x \ klin y \ klin z) ~}$

W najgorszym przypadku dane wejściowe (dla każdego algorytmu) to 1, 1, 1. W każdej kolejności sprawdzania zmiennych musimy sprawdzić wszystkie. (Zauważ, że generalnie dla każdego algorytmu drzewa decyzyjnego może istnieć inny najgorszy przypadek.) Stąd funkcje: „i”, „lub” (dla n zmiennych ) są wymijające.

Binarne gry o sumie zerowej

W przypadku binarnych gier o sumie zerowej każda funkcja ewaluacyjna jest wymijająca.

W każdej grze o sumie zerowej wartość gry jest osiągana przez algorytm minimax (gracz 1 stara się zmaksymalizować zysk, a gracz 2 stara się zminimalizować koszt).

W przypadku binarnym funkcja max jest równa bitowemu „lub”, a funkcja min jest równa bitowemu „i”.

Drzewo decyzyjne dla tej gry będzie miało następującą postać:

• każdy liść będzie miał wartość w {0, 1}.
• każdy węzeł jest połączony z jednym z {"and", "or"}

Dla każdego takiego drzewa z n liśćmi czas działania w najgorszym przypadku wynosi n (co oznacza, że ​​algorytm musi sprawdzić wszystkie liście):

Pokażemy przeciwnika , który generuje dane wejściowe w najgorszym przypadku – dla każdego liścia sprawdzanego przez algorytm przeciwnik odpowie 0, jeśli rodzicem liścia jest węzeł Or, i 1, jeśli rodzicem jest węzeł And.

To wejście (0 dla wszystkich dzieci węzłów Or i 1 dla wszystkich dzieci węzłów And) zmusza algorytm do sprawdzenia wszystkich węzłów:

Jak w drugim przykładzie

• aby obliczyć wynik LUB , jeśli wszystkie dzieci mają wartość 0, musimy je wszystkie sprawdzić.
• Aby obliczyć wynik I , jeśli wszystkie dzieci są równe 1, musimy je wszystkie sprawdzić.

Zobacz też

• Przypuszczenie Aanderaa – Karpa – Rosenberga , przypuszczenie, że każda nietrywialna właściwość grafu monotonicznego jest wymijająca.