Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?

13

Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie ukierunkowanym występuje niewyważony wierzchołek, musi istnieć inny. Ale zazwyczaj klasa jest formalnie zdefiniowana w kategoriach problemu ( ), w którym argument jest stosowany tylko do wykresów z wejściami i przejściami . Moje pytanie brzmi: dlaczego te pojęcia są równoważne?ANOTHER END OF THE LINEAEOL1

Do tego momentu jest to duplikat tego pytania . Teraz chcę sformułować problem formalnie i wyjaśnić, dlaczego nie jestem zadowolony z udzielonej tam odpowiedzi.

Problem wyszukiwania ( ): otrzymujemy dwa obwody wielomianowe i które otrzymują i zwracają listę wielomianową inne elementy w . Obwody te definiują ukierunkowany wykres gdzie i . Problem wyszukiwania jest następujący: biorąc pod uwagę , i tak, że , znajduje inny wierzchołek o tej samej właściwości.ANOTHER UNBALANCED VERTEXAUVSPx{0,1}n{0,1}nG=(V,E)V={0,1}n(x,y)E(yS(x)xP(y))SPzVindegree(z)outdegree(z)

Problem wyszukiwania : to samo, ale zarówno jak i zwracają pustą listę lub jeden element.AEOLSP

Pojęcie redukowalności (skorygowane zgodnie z sugestią Ricky'ego): całkowity problem wyszukiwania można sprowadzić do całkowitego problemu wyszukiwania za pomocą funkcji wielomianu i jeżeli jest rozwiązaniem w problemie implikuje, że jest rozwiązaniem PROBLEM . B f g y f ( x ) B g ( x , y ) x AABfgyf(x)Bg(x,y)xA

Formalne pytanie : dlaczego zredukować do ? A może powinniśmy użyć innego pojęcia redukowalności?A E O LAUVAEOL

Christos Papadimitriou dowodzi analogicznego twierdzenia o PPA (Twierdzenie 1, strona 505), ale wydaje się, że argument ten nie działa na PPAD . Powodem jest to, że wierzchołek o równowadze stopni zostanie przekształcony w wierzchołków o równowadze stopni . Następnie algorytm dla może uzyskać jeden z tych wierzchołków i zwrócić inny. Nie dałoby to nowego wierzchołka dla .k ± 1 A E O L A U V±kk±1AEOLAUV

Gorzej, bo w zawsze jest parzysta liczba niezrównoważonych wierzchołków, ale w może być ich nieparzysta liczba. Dlatego nie można zbudować bijectionu między tymi dwoma zbiorami nie zawsze może być równe . Jeśli to otrzymujemy metodę rozwiązywania w czasie wielomianowym przynajmniej w niektórych przypadkach. Jeśli nie zależy od i dla następnie mogą być zwrócone w odpowiedzi na . To nie dałoby rozwiązaniaA U V g f - 1 g ( x , f ( x ) ) x A U V g x g ( y 1 ) = g ( y 2 ) y 1y 2 y 2 y 1 A U VAEOLAUVgf1g(x,f(x))xAUVgxg(y1)=g(y2)y1y2y2y1AUV .

Ostatnie pytanie : czy można jakoś pokonać powyższe przeszkody? Czy można zastosować możliwą zależność od ?xgx

Daniil Musatov
źródło
2
„dlaczego te pojęcia są równoważne?” Z powodów podanych w dowodzie Twierdzenia 1 na stronie 505 autorstwa Christosa Papadimitriou. (W przeciwnym razie, jak myślisz, co jest argumentem parzystości dla całości AUV?) Twoja definicja redukowalności wydaje się zbyt silna - Na przykład, zgodnie z twoją definicją, rozszerzenie zestawu rozwiązań może znacznie utrudnić całkowity problem wyszukiwania.
2
+1 i -1 mają tę samą parzystość. (Ta parzystość jest „nieparzysta”.) Właściwa ma „implikuje ” zamiast „iff ”. g (g(x,y)g(y)
2
Teraz to, co nie jest to, że będę go nazywać UnbalancedInOtherDirectionVertex, że problem sprowadza się do PPADS , ponieważ można odwrócić krawędzie jeśli to konieczne, aby dany wierzchołek mają większą poza stopień niż w-stopnia, a następnie całkowity -degree-1 wierzchołki, w które dany wierzchołek zostanie przekształcony, będą wszystkie źródłami, a nie tonami. Nie widzę podobnego sposobu przejścia od problemu do AEOL. k
1
Przynajmniej zmniejszenie pokazuje, że AUV jest równoważne z jego przypadkiem, w którym wszystkie wierzchołki mają stopień niezależny i co najwyżej 1 stopień, z wyjątkiem ewentualnie danego wierzchołka z, który ma stopień 0, ale może mieć duży stopień stały.
Emil Jeřábek
2
Właśnie usłyszałem od Frederica Meuniera, że ​​zauważył ten problem pięć lat temu i Papadimitriou się zgodził.
domotorp

Odpowiedzi:

4

To interesujące pytanie i mogę jedynie udzielić częściowej odpowiedzi.

Łatwo zauważyć, że konstrukcja na str. 505 pracy Papadimitriou pokazuje równoważność AUV z jej szczególnym przypadkiem

WIELE KOŃCÓW LINII (MEOL): Biorąc pod uwagę ukierunkowany wykres z co najwyżej 1 stopniem i stopniem (reprezentowanym przez obwody jak powyżej) oraz niepustym zbiorem X źródeł G , znajdź ujście lub źródło v X .G1XGvX

Z jednej strony trudno mi sobie wyobrazić transformację takich grafów, która mogłaby zredukować większą liczbę źródeł do jednego.

Jednak z drugiej strony MEOL należy do wszystkich powszechnie badanych klas zawierających PPAD, z wyjątkiem ewentualnie samego PPAD :

Po pierwsze, oczywiście

MEOL jest w PPADS .

Naszkicuję poniżej argument, że

MEOL jest w PPA

przez redukcję do standardowego problemu pełnego PPA (nieukierunkowanej wersji AEOL ). Załóżmy, że podano i X jak w definicji MEOL.G=(V,E)X

Jeśli jest dziwne, możemy po prostu sprawić, że wykres nie zostanie przekierowany, dołączymy dopasowanie do wszystkich wierzchołków X z wyjątkiem jednego (jak w argumencie na str. 505) i przekażemy wynik wraz z pozostałym źródłem z X do wyroczni PPA .|X|XX

Ogólnie rzecz biorąc, niech , a 2 k będzie największą potęgą 2 dzielącą s . Definiujemy nowy wykres G = ( V , E ), którego wierzchołki są podzbiorami V k 2- elementowymi . Jeśli A , B V są takimi zbiorami, umieszczamy krawędź ( A , B ) w E ′, jeśli możemy wyliczyć zbiory jako A =s=|X|2k2sG=(V,E)2kVA,BV(A,B)E , B = { b 0 , , b 2 k - 1 } w taki sposób, że ( a i , b i ) E dla każdego i < 2 k .A={a0,,a2k1}B={b0,,b2k1}(ai,bi)Ei<2k

Oczywiście, jest skierowany wykres zw stopnia i poza stopień najwyżej 1 . V " jest źródłem (umywalka) iff zawiera źródło (umywalka, odpowiednio.) O G . (Oznacza to, że jeśli zawiera oba, jest to izolowany wierzchołek.) Tak więc każdy taki wierzchołek prowadziłby do rozwiązania instancji MEOL , chyba że A jest „znanym źródłem”: to znaczy A X . Zamierzamy sprawić, by wykres nie był przekierowywany i manipulowaliśmy nim tak, aby liczba znanych źródeł została zmniejszona do 1 , włączając dopasowanie do pozostałych.G1AVGAAX1

Jeśli więc jest znanym źródłem, niech t = | A X | , który spełnia 0 < t 2 k . Jeśli t = 2 k = | A | , Wystarczy X . Liczba takich zestawów wynosi ( sAt=|AX|0<t2kt=2k=|A|AX. Przypomnijmy, że wielokrotność liczby pierwszejpw(a(s2k)p równa się liczbie przeniesień w dodatkub+(a-b)=awykonane w podstawiep. Z wyborukwynika, że ( s(ab)b+(ab)=apkjest nieparzysty. Co więcej, istnieją bijectacje w czasie wielomianowym pomiędzy[0,(a(s2k)ipodzbioryb-elementowe z[0,a). Korzystanie z tym, możemy zdefiniować wielomian dopasowania czasu na wszystko, ale jeden z2k-elementowe podzbiorówX. Uwzględniamy to na wykresie, co zmniejsza liczbę znanych źródeł przyt=2kdo1.[0,(ab))b[0,a)2kXt=2k1

Dla wzór liczenia przeniesień pokazuje, że ( s0<t<2k jest parzysty. Ponownie możemy znaleźć wyraźne dopasowanie nat-elementowe podzbiorówX. Rozszerzamy go na znane źródłaA zapomocą| AX| =tpoprzez zastosowanie dopasowania doAXi pozostawienieAX nastałym poziomie.(st)tXA|AX|=tAXAX

W ten sposób tworzymy wykres bezkierunkowy z jednym znanym wierzchołkiem liścia. Prosimy o wyrocznię PPA o kolejny liść, a ze względu na budowę możemy wyciągnąć z niego odpowiedź dla instancji MEOL .


Jak krótko wspomniał Papadimitriou, możemy uogólnić PPA do klas PPA - dla dowolnej liczby pierwszej p . Przykładem kompletnego problemu PPA - p jestppp

AUV - : Biorąc pod uwagę ukierunkowany wykres G i wierzchołek, którego równowaga stopni wynosipG , znajdź kolejny taki wierzchołek.0(modp)

(Zobacz odpowiedź na równoważność AUV - z definicją PPA Papadimitriou - p .)pp

PPA - to tylko PPA . Przyjmuje się, że klasy PPA - p są nieporównywalne parami i nieporównywalne z PPADS . Wszystkie zawierają PPAD .2p

W przedstawionym powyżej argumencie nie było nic szczególnego i można go łatwo zmodyfikować, aby uzyskaćp=2

MEOL jest w PPA - dla każdej liczby pierwszej p .pp

Emil Jeřábek
źródło
Bardzo podoba mi się odpowiedź i postanowiłem ją zaakceptować (oczywiście bardziej kompletne odpowiedzi są nadal mile widziane). Myślę tylko, że klasa reprezentowana przez AUV - powinna nazywać się PPAD - p . Papadimitriou pisze o nieukierowanych dwustronnych grafach i tylko stopniach, a nie równowagach. pp
Daniil Musatov
3
Klasy są uogólnieniami PPA, a nie PPAD, dla . Papadimitriou daje inny kompletny problem niż AUV- p (zauważ, że jego wykresy są dwustronne), ale jest to odpowiednik mojej definicji. Cały schemat nazewnictwa jest strasznie mylący; zastosowanie grafów skierowanych i niekierowanych dla konkretnej klasy jest tylko przypadkiem, wiele klas ma kompletne problemy dotyczące zarówno grafów skierowanych, jak i niekierowanych (jak w przypadku PPA- p ). Ponadto, pomimo ich nazw, większość klas nie opiera się na argumentach parzystości, ale na innych zasadach liczenia. Tylko PPA dotyczy parytetu. p=2pp
Emil Jeřábek
Dzięki, rozumiem. To rzeczywiście ta sama klasa. Słyszałem spekulacje, że Papadimitriou wybrał imię PPAD, ponieważ przypomina ono jego własne nazwisko.
Daniil Musatov
Czy masz referencje dotyczące PPAD w PPA-p?
domotorp
1
Nie jest to jednoznaczne, ale na przykład definiowanie problemu pełnego PPAD jest dosłownie szczególnym przypadkiem AUV- . p
Emil Jeřábek