Dlaczego te dwie definicje PPAD są równoważne?

Klasa złożoności PPAD jest zwykle definiowana przez stwierdzenie, że Koniec linii jest kompletny z PPAD.

Koniec linii to problem z wyszukiwaniem. Dane wejściowe składają się z ukierunkowanego wykresu, w którym każdy węzeł ma co najwyżej stopień i stopień 1. Wykres jest podawany przez funkcję obliczeniową wielomianową która zwraca poprzednika i następcę x . Ponadto jeden otrzymuje węzeł v z następcą, ale bez poprzednika. Znajdź węzeł t ≠ v, który nie ma następcy lub poprzednika.$f(x)$$x$$v$$t\ne v$

Ostatnio słyszałem inną definicję PPAD. O ile pamiętam, było to oparte na następującym problemie.

Podany jest wykres ukierunkowany (ponownie określony przez funkcję obliczalną czasu wielomianowego) i węzeł, którego stopień nie jest równy, jego stopień jest podany. Znajdź inny węzeł z tą właściwością.

Oczywiście koniec linii jest specjalnym przypadkiem tego drugiego problemu, ale czy ten ostatni problem jest naprawdę trudniejszy do rozwiązania? Moje pytanie brzmi:

Czy oba problemy są kompletne dla tej samej klasy złożoności PPAD? Jeśli tak, dlaczego? Jeśli nie, jaka jest klasa złożoności wynikająca z drugiego problemu?

W przypadku problemów z cytowanym referatem (i stąd ta odpowiedź) zobacz Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?

Tak. Te dwa problemy są równoważne, a zatem pełne PPAD. Zmniejszenie podano na stronie 505 oryginalnego Papadimitriou z 1994 r dokumentu ( Pdf ), w którym wprowadzono koniec linii . Jest to ważne, nawet jeśli stopień wykresu jest wykładniczy, pod warunkiem, że otrzymamy „algorytm rozpoznawania krawędzi” i „funkcję parowania”. Jest to również wspomniane na tej samej stronie. Zmniejszenie dotyczy PPA (nieukierunkowanej wersji PPAD). Można go również rozszerzyć na PPAD.