Pozytywne uporządkowanie topologiczne, weź 2

Jest to kontynuacja ostatniego pytania Davida Eppsteina i jest motywowana tymi samymi problemami.

Załóżmy, że mam wierzchołek z ciężarami na liczbach rzeczywistych na jego wierzchołkach. Początkowo wszystkie wierzchołki są nieoznaczone. Mogę zmienić zestaw zaznaczonych wierzchołków, albo (1) zaznaczając wierzchołek bez nieoznaczonych poprzedników, albo (2) odznaczając wierzchołek bez zaznaczonych następców. (Zatem zestaw zaznaczonych wierzchołków jest zawsze przedrostkiem częściowej kolejności). Chcę znaleźć sekwencję operacji oznaczania / odznaczania, która kończy się na wszystkich zaznaczonych wierzchołkach, tak że całkowita waga zaznaczonych wierzchołków jest zawsze nieujemna .

• Jak trudno jest znaleźć taką sekwencję operacji? W przeciwieństwie do problemu Davida , nie jest nawet jasne, że ten problem dotyczy NP; w zasadzie (chociaż nie mam żadnych przykładów) każda legalna sekwencja ruchów może mieć wykładniczą długość. Najlepsze, co mogę udowodnić, to to, że problem dotyczy PSPACE.

• Czy operacja odznaczania jest rzeczywiście niepotrzebna? Jeśli istnieje poprawna sekwencja ruchów, czy musi istnieć poprawna sekwencja ruchów, która nigdy nie odznacza wierzchołka? Odpowiedź twierdząca sprawi, że problem ten będzie identyczny jak w przypadku Davida . Z drugiej strony, jeśli czasem odznaczanie jest czasem konieczne, powinien istnieć mały (stały rozmiar) przykład, który to potwierdza.

Podczas naszego regularnego seminarium badawczego 666 przedstawiliśmy następujący dowód.

Zaczynamy od niektórych definicji. Niech P będzie naszym zestawem. Dla uproszczenia załóżmy, że żadna z wag nie sumuje się do zera. Oznacz wagę wierzchołka przez w (x) i sumę wag zbioru przez w (X). Mówimy, że zbiór X jest Y-up (zamknięty), jeśli jest zawarty w Y, a każdy element Y, który jest większy niż element X, również znajduje się w X. Podobnie, powiedzmy, że zbiór X jest Y-down, jeśli jest zawarty w Y, a każdy element Y, który jest mniejszy niż element X, również znajduje się w X. W tym języku zestaw zaznaczonych elementów musi być zawsze w dół.

Udowadniamy przez sprzeczność. Wybierz najkrótszą sekwencję oznaczania / odznaczania, która oznacza każdy element. Takie sekwencje nazywamy pełnymi. W dowolnym momencie rozważ zestaw elementów, które były wcześniej zaznaczone, ale teraz są nieoznaczone. Oznacz ten zestaw przez U.

Roszczenie: w (U)> 0.

Dowód: Udowadniamy, że waga każdego zestawu U-up, X, jest dodatnia. Dowodem jest indukcja wielkości X. Jeśli istnieje zbiór X-dół, Y, taki, że w (Y)> 0, to skoro dzięki indukcji wiemy, że w (X \ Y)> 0 (ponieważ jest to X-up), mamy również w (X)> 0. Jeśli dla każdego zbioru X-dół, Y, mamy w (Y) <0, to usuwając do tego momentu wszystkie oznaczenia i odznaczenia elementów X z naszej sekwencji, otrzymujemy krótszą pełną sekwencję. Skończyliśmy z dowodem roszczenia.

Załóżmy teraz, że mamy pełną sekwencję, w której w (U)> 0 w dowolnym punkcie dla zbioru U aktualnie nieoznaczonych elementów. Weź sekwencję, którą otrzymujemy, biorąc pierwsze oznaczenie każdego elementu i nigdy nie odznaczając niczego. Oczywiste jest, że będzie to również pełna sekwencja spełniająca fakt, że zestaw zaznaczonych elementów ma zawsze wartość P-dół. Co więcej, suma wag będzie zawsze przynajmniej taka sama jak w oryginalnej sekwencji, ponieważ w danym momencie różnica wynosi w (U). Skończyliśmy.

Za pomocą tej metody można nawet udowodnić, że jeśli zamiast zaznaczać całe P, chcemy jedynie zaznaczyć podzbiór P, można to zrobić za pomocą sekwencji oznaczeń, a następnie sekwencji odznaczeń. Dowód jest taki sam, z tym wyjątkiem, że na końcu niektóre elementy U pozostają niezaznaczone, ale można je przenieść na koniec sekwencji, ponieważ waga dowolnego zestawu U-up jest dodatnia.