Erfasst PPAD wirklich den Gedanken, einen anderen unausgeglichenen Scheitelpunkt zu finden?

13

Die Komplexitätsklasse PPAD wurde von Christos Papadimitriou in seiner wegweisenden Arbeit von 1994 erfunden . Die Klasse soll die Komplexität von Suchproblemen erfassen, bei denen die Existenz einer Lösung durch "Paritätsargument in gerichteten Diagrammen" garantiert wird: Wenn ein gerichteter Graph einen unausgeglichenen Scheitelpunkt enthält, muss ein anderer vorhanden sein. Aber in der Regel wird die Klasse formal in Bezug auf den definierten A N O T H E R E N D O F T H E L I N E    ANOTHER END OF THE LINE ( ) Problem, wo das Argument nur mit sowohl zu Graphen angewendet wird - und outdegreesA E O LAEOL11 . Meine Frage ist: Warum sind diese Begriffe gleichwertig?

Bis zu diesem Punkt ist es ein Duplikat dieser Frage . Jetzt möchte ich das Problem formell darlegen und klären, warum ich mit der Antwort dort nicht zufrieden bin.

Suchproblem ( ): Wir erhalten zwei Schaltungen und , die und eine polynomielle Liste von zurückgeben andere Elemente in . Diese Schaltungen definieren einen gerichteten Graphen wobei und . Das Suchproblem ist das folgende: , und so gegeben sind, dass , finde einen anderen Scheitelpunkt mit der gleichen Eigenschaft.A N O T H E R U N B A L A N C E D V E R T E X   ANOTHER UNBALANCED VERTEXA U VAUV S SP Px { 0 , 1 } nx{0,1}n { 0 , 1 } n{0,1}n G = ( V , E ) G=(V,E)V = { 0 , 1 } nV={0,1}n ( x , y) E ( y S ( x ) x P ( y ) ) S P z V i n d e g r e e ( z ) o u t d e g r e e ( z )(x,y)E(yS(x)xP(y))SPzVindegree(z)outdegree(z)

Suchproblem : dasselbe, aber sowohl als auch geben entweder eine leere Liste oder ein Element zurück.A E O L S PAEOLSP

Der Begriff der Reduzierbarkeit (korrigiert nach Rickys Vorschlag): Gesamtsuchproblem ist reduzierbar auf Gesamtsuchproblem über Polynomfunktionen und , wenn eine Lösung ist in Problem impliziert ist , eine Lösung für x in Problem A . A B f g y f ( x ) B g ( x , y ) x AABfgyf(x)Bg(x,y)xA

Formale Frage : Warum kann A U VAUV auf \ mathsf {AEOL} reduziert werden A E O LAEOL? Oder sollten wir einen anderen Begriff der Reduzierbarkeit verwenden?

Christos Papadimitriou beweist einen analogen Satz über PPA (Satz 1, Seite 505), aber das Argument scheint für PPAD nicht zu funktionieren . Der Grund ist, dass ein Vertex mit dem Gradgleichgewicht in Vertices mit dem transformiert wird . Dann kann der Algorithmus für einen dieser Eckpunkte erhalten und einen anderen zurückgeben. Dies würde keinen neuen Vertex für .± k k ± 1 A E O L A U V±kk±1AEOLAUV

Die Dinge werden immer schlimmer, weil es in immer eine gerade Anzahl von unausgeglichenen Eckpunkten gibt, aber in es eine ungerade Anzahl von ihnen geben. Dies ist der Grund, warum man keine Bijektion zwischen diesen beiden Mengen aufbauen kann und nicht immer gleich . Wenn dann erhalten wir zumindest für einige Fälle eine Methode zum Lösen von in der Polynomzeit. Wenn hängt nicht von und für dann kann als Antwort zurückgegeben werden . Das würde keine Lösung für gebenAEOLAEOLAUVAUVggf1f1g(x,f(x))xg(x,f(x))xAUVAUVggxxg(y1)=g(y2)g(y1)=g(y2)y1y2y1y2y2y2y1y1AUVAUV .

Letzte Frage : Können die oben genannten Hindernisse irgendwie überwunden werden? Kann man eine mögliche Abhängigkeit von von anwenden ?ggxx

Daniil Musatov
quelle
2
"Warum sind diese Begriffe gleichwertig?" Aus den im Beweis von Satz 1 auf Seite 505 von Christos Papadimitriou angegebenen Gründen. (Was ist Ihrer Meinung nach ansonsten ein Paritätsargument für die Gesamtheit der AUV?) Ihre Definition der Reduzierbarkeit scheint zu stark zu sein. Wenn Sie beispielsweise die Menge der Lösungen erweitern, kann dies ein Gesamtsuchproblem erheblich erschweren.
2
+1 und -1 haben die gleiche Parität. (Diese Parität ist "ungerade".) Die rechte hat "impliziert " anstelle von "iff " ". g(x,y)g(x,y)g(y)g(y)
2
Was wir jetzt haben, ist, dass, ich nenne es UnbalancedInOtherDirectionVertex, dieses Problem auf PPADS reduziert wird , da man die Kanten bei Bedarf spiegeln kann, um den gegebenen Scheitelpunkt einen größeren Out-Degree als In-Degree zu haben, und dann den Total -degree-1-Eckpunkte, in die der angegebene Eckpunkt transformiert wird, sind alle Quellen und keine Senken. Ich sehe keinen ähnlichen Weg von Ihrem Problem zu AEOL. kk
1
Zumindest die Reduktion zeigt, dass AUV äquivalent zu dem Fall ist, in dem alle Eckpunkte höchstens 1 Grad und 1 Grad haben, mit Ausnahme möglicherweise des gegebenen Eckpunkts z, der 0 Grad hat, aber einen großen Außengrad haben kann.
Emil Jeřábek unterstützt Monica
2
Ich habe gerade von Frederic Meunier gehört, dass er dieses Problem auch vor fünf Jahren beobachtet hat, und Papadimitriou stimmte zu.
Domotorp

Antworten:

4

Dies ist eine interessante Frage, die ich nur teilweise beantworten kann.

Es ist leicht zu sehen, dass die Konstruktion auf p. 505 von Papadimitrious Aufsatz zeigt die Gleichwertigkeit von AUV mit seinem Sonderfall

VIELE ENDEN DER LINIE (MEOL): Wenn ein gerichteter Graph G mit einem In-Grad und einem Out-Grad von höchstens 1 (dargestellt durch die obigen Schaltkreise) und eine nicht leere Menge X von Quellen von G gegeben ist , finde eine Senke oder eine Quelle v X .G1XGvX

Einerseits fällt es mir schwer, mir eine Transformation solcher Graphen vorzustellen, die eine größere Anzahl von Quellen auf eine reduzieren könnte.

Andererseits gehört MEOL zu allen allgemein untersuchten Klassen, die PPAD enthalten, außer möglicherweise PPAD selbst:

Erstens offensichtlich

MEOL ist in PPADS .

Ich werde im Folgenden ein Argument skizzieren, das

MEOL ist in PPA

durch Reduktion auf das Standard- PPA- Problem (die ungerichtete Version von AEOL ). Angenommen, wir haben G = ( V , E ) und X wie in der Definition von MEOL.G=(V,E)X

Wenn | X | Ist dies ungerade, können wir den Graphen einfach ungerichtet machen, eine Übereinstimmung für alle Scheitelpunkte bis auf einen von X einschließen (wie im Argument auf S. 505) und das Ergebnis zusammen mit der verbleibenden Quelle von X an das PPA- Orakel übergeben.|X|XX

Im Allgemeinen sei s = | X | und 2 k ist die größte Potenz von 2 , die s teilt . Wir definieren einen neuen Graphen G ' = ( V ' , E ' ), dessen Eckpunkte 2 k- Element-Teilmengen von V sind . Wenn A , B V ' solche Mengen sind, setzen wir die Kante ( A , B ) in E ', wenn wir die Mengen als A = aufzählen könnens=|X|2k2sG=(V,E)2kVA,BV(A,B)E{ a 0 , , a 2 k - 1 } , B = { b 0 , , b 2 k - 1 } auf solche Weise, dass ( a i , b i ) E für jedes i < 2 k ist .A={a0,,a2k1}B={b0,,b2k1}(ai,bi)Ei<2k

Es ist klar, dass G ' ein gerichteter Graph mit höchstens 1 In-Grad und Out-Grad ist . Ein A V ' ist eine Quelle (Senke), wenn es eine Quelle (Senke) von G enthält . (Das heißt, wenn es sowohl enthält, ist es eine isolierte Ecke.) , So ist jede solche Scheitelpunkt zu einer Lösung des führen würde MeOL Beispiel, es sei denn , A eine „bekannte Quelle“ ist: das heißt, A X & ne; . Wir beabsichtigen, den Graphen ungerichtet zu machen und ihn so zu manipulieren, dass die Anzahl der bekannten Quellen auf 1 reduziert wird, indem eine Übereinstimmung für die verbleibenden eingeschlossen wird.G1AVGAAX1

Also, wenn A eine bekannte Quelle ist, sei t = | A X | , die 0 < t 2 k erfüllt . Wenn t = 2 k = | A | , Dann einfach A X . Die Anzahl solcher Sätze ist ( sAt=|AX|0<t2kt=2k=|A|AX2 k ). Denken Sie daran, dass die Multiplizität einer Primzahlpin(a(s2k)pb ) entspricht der Anzahl der Überträge in der Additionb+(a-b)=a,die in der Basisp durchgeführt wird. Durch die Wahl vonkfolgt ( s(ab)b+(ab)=apk2 k )ist ungerade. Darüber hinaus gibt es Polynomzeit-Bijektionen zwischen[0,(a(s2k)b ) )undb-Element-Teilmengen von[0,a). Auf diese Weise können wir eine Polynomzeitanpassung für alle bis auf eine von2k-Element-Teilmengen vonX definieren. Wir nehmen es in den Graphen auf, der die Anzahl der bekannten Quellen mitt=2kauf1reduziert.[0,(ab))b[0,a)2kXt=2k1

Für 0 < t < 2 k zeigt die Carry-Counting-Formel, dass ( s0<t<2kt ) ist gerade. Auch hier können wir eine explizite Übereinstimmung fürt-Element-Teilmengen vonX finden. Wir erweitern es auf bekannte QuellenAmit| AX| =Tdurch die Anpassung anAnwendungAXund VerlassenAXfixiert.(st)tXA|AX|=tAXAX

Auf diese Weise erzeugen wir einen ungerichteten Graphen mit einem bekannten Scheitelpunkt. Wir bitten das PPA- Orakel um ein anderes Blatt und können konstruktionsbedingt eine Antwort für die MEOL- Instanz daraus extrahieren .


Wie bereits kurz von Papadimitriou erwähnt, können wir verallgemeinern PPA Klassen PPA - p für jede Primzahl p . Ein Beispiel für ein PPA - p - vollständiges Problem istppp

AUV - p : Gegeben ist ein gerichteter Graph G und ein Scheitelpunkt, dessen Gradbilanz gleich istpG0( modp ) , finde einen anderen solchen Eckpunkt.≢0(modp)

(Siehe diese Antwort für die Äquivalenz von AUV - p mit Papadimitrious Definition von PPA - p .)pp

PPA - 2 ist nur PPA . Es wird angenommen, dass die Klassen PPA - p paarweise nicht vergleichbar und mit PPADS nicht vergleichbar sind . Sie alle enthalten PPAD .2p

P = 2 war in dem oben skizzierten Argument nicht besonders speziell , und es kann leicht modifiziert werden, um zu ergebenp=2

MEOL ist in PPA - p für jede Primzahl p .

Emil Jeřábek unterstützt Monica
quelle
Ich mag die Antwort sehr und habe beschlossen, sie anzunehmen (natürlich sind noch vollständigere Antworten willkommen). Ich denke nur, dass die von AUV - p dargestellte Klasse PPAD - p heißen sollte . Papadimitriou schreibt über ungerichtete zweigeteilte Graphen und nur Grad, nicht Gleichgewichte.
Daniil Musatov
3
Die Klassen sind Verallgemeinerungen von PPA und nicht von PPAD für p = 2 . Papadimitriou gibt ein anderes vollständiges Problem an als AUV- p (beachte, dass seine Graphen zweigeteilt sind), aber es entspricht meiner Definition. Das ganze Benennungsschema ist furchtbar verwirrend; die Verwendung von gegen ungerichtete Graphen für eine bestimmte Klasse gerichtet ist nur ein Unfall, viele der Klassen haben die vollständigen Probleme in Bezug auf den beide gerichteten und ungerichteten Graphen (wie im Fall von PPA- p ). Außerdem basieren die meisten Klassen trotz ihrer Namen nicht auf Paritätsargumenten, sondern auf anderen Zählprinzipien. Nur bei PPA geht es um Parität.
Emil Jeřábek unterstützt Monica
Danke, verstanden. Es ist in der Tat die gleiche Klasse. Ich habe eine Spekulation gehört, dass Papadimitriou den Namen PPAD gewählt hat, weil er seinem eigenen Nachnamen ähnelt.
Daniil Musatov
Haben Sie eine Referenz für PPAD in PPA-p?
Domotorp
1
Nicht explizit ein, sondern zum Beispiel die Definition von PPAD-vollständigen Problem ist buchstäblich ein Spezialfall von AUV- p .
Emil Jeřábek unterstützt Monica