Warum sind diese beiden Definitionen von PPAD gleichwertig?

13

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)xvtv

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?

Matthias
quelle

Antworten:

15

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.

Shiva Kintali
quelle
3
Ich habe Probleme, das Argument auf PPAD auszudehnen. Im ursprünglichen Beweis werden neue Scheitelpunkte erzeugt, indem Kantenpaare desselben alten Scheitelpunkts kombiniert werden. Für PPAD ist es selbstverständlich, eingehende und ausgehende Kanten zu kombinieren. Dann ist jedoch nicht mehr garantiert, dass jeder unausgeglichene alte Scheitelpunkt nur einen unausgeglichenen neuen Scheitelpunkt erzeugt. Und wenn es viele von ihnen gibt, kann eine Suche in dem neuen Diagramm einen anderen neuen Scheitelpunkt zurückgeben, der von demselben alten Scheitelpunkt erzeugt wird. Dies gibt keine Antwort auf das ursprüngliche Problem. Wie kann man diese Schwierigkeiten überwinden?
Daniil Musatov