Warum sind diese beiden Definitionen von PPAD gleichwertig?

Die Komplexitätsklasse PPAD wird normalerweise definiert, indem angegeben wird, dass End-Of-The-Line PPAD-vollständig ist.

End-Of-The-Line ist ein Suchproblem. Die Eingabe besteht aus einem gerichteten Graphen, in dem jeder Knoten höchstens 1 In-Grad und Out-Grad hat. Der Graph wird durch eine Polynomzeit-berechenbare Funktion , die den Vorgänger und Nachfolger von x zurückgibt . Außerdem erhält man einen Knoten v mit einem Nachfolger, aber keinem Vorgänger. Finden Sie einen Knoten t ≠ v , die keinen Nachfolger oder keinen Vorgänger hat.$f(x)$$x$$v$$t\ne v$

Kürzlich hörte ich eine andere Definition von PPAD. Soweit ich mich erinnere, lag das folgende Problem zugrunde.

Es wird ein gerichteter Graph (der wiederum durch eine berechenbare Polynomzeitfunktion spezifiziert ist) und ein Knoten angegeben, dessen In-Grad ungleich seinem Out-Grad ist. Suchen Sie einen anderen Knoten mit dieser Eigenschaft.

Offensichtlich ist End-Of-The-Line ein Sonderfall des letzteren Problems, aber ist das letztere Problem wirklich schwieriger zu lösen? Meine Frage lautet:

Sind beide Probleme für dieselbe Komplexitätsklasse PPAD abgeschlossen? Wenn ja warum Wenn nein, welche Komplexitätsklasse ergibt sich aus dem zweiten Problem?

Zu Problemen mit dem zitierten Artikel (und damit dieser Antwort) siehe Erfasst PPAD wirklich den Gedanken, einen anderen unausgeglichenen Scheitelpunkt zu finden?

Ja. Diese beiden Probleme sind äquivalent und daher PPAD-vollständig. Die Reduktion wird auf Seite 505 von Papadimitriou ursprünglichen 1994 Papier ( pdf ) Einführung Ende der Linie . Dies gilt auch dann, wenn der Grad des Graphen exponentiell ist, vorausgesetzt, wir haben einen "Kantenerkennungsalgorithmus" und eine "Paarungsfunktion". Dies wird auch auf derselben Seite erwähnt. Die Ermäßigung gilt für PPA (die ungerichtete Version von PPAD). Es kann auch auf PPAD erweitert werden.