Tworzymy strategie dla adwersarza dla programu, który sprawdza wynik w drzewie.
Idukcyjnie po strukturze drzewa, pokażemy, że w każdym poddrzewie potrafimy dla danego algorytmu przeciwnika A, który dfsuje, zmusić go do odwiedzenia wszystkich wierzchołków i w dodatku do uzyskania wyniku jaki chcemy w korzeniu drzewa.
Baza: Drzewa w postaci (liść\;OR\;liść\;OR\;\dots\;OR\;liść). Na zapytania o pierwsze n-1 liści tego drzewa odpowiadamy 0. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego liścia. Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.
Krok I: Drzewa w postaci (drzewo\;AND\;drzewo\;AND\;\dots\;AND\;drzewo). Na zapytania o pierwsze n-1 poddrzew tego drzewa wymuszamy 1 w tym poddrzewie. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego poddrzewa. Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.
Krok II: Drzewa w postaci (drzewo\;OR\;drzewo\;OR\;\dots\;OR\;drzewo). Na zapytania o pierwsze n-1 poddrzew tego drzewa wymuszamy 0 w tym poddrzewie. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego poddrzewa. Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.
Liści w drzewie d-arnym o wysokości 2k jest d^{2k}, algorytm A odwiedza wszystkie.
Tworzymy strategie dla adwersarza dla programu, który sprawdza wynik w drzewie.
Idukcyjnie po strukturze drzewa, pokażemy, że w każdym poddrzewie potrafimy dla danego algorytmu przeciwnika A, który dfsuje, zmusić go do odwiedzenia wszystkich wierzchołków i w dodatku do uzyskania wyniku jaki chcemy w korzeniu drzewa.
Baza: Drzewa w postaci maj(liść,liść,liść). Na zapytania o pierwsze 2 liście tego drzewa odpowiadamy 0,1. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego liścia. Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.
Krok: Drzewa w postaci maj(drzewo,drzewo,drzewo). Na zapytania o pierwsze 2 poddrzewa tego drzewa wymuszamy 0,1.w tych poddrzewie. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego poddrzewa. Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.
Odwiedzamy wszystkie 3^h liście.