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

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?$\mathsf{ANOTHER\ END\ OF\ THE\ LINE}$$\mathsf{AEOL}$$\le 1$

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.$\mathsf{ANOTHER\ UNBALANCED\ VERTEX}$$\mathsf{AUV}$$S$$P$$x\in\{0,1\}^n$$\{0,1\}^n$$G=(V,E)$$V=\{0,1\}^n$$(x,y)\in E\Leftrightarrow (y\in S(x)\land x\in P(y))$$S$$P$$z\in V$$indegree(z)\ne outdegree(z)$

Problem wyszukiwania : to samo, ale zarówno jak i zwracają pustą listę lub jeden element.$\mathsf{AEOL}$$S$$P$

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 $A$$B$$f$$g$$y$$f(x)$$B$$g(x,y)$$x$$A$

Formalne pytanie : dlaczego zredukować do ? A może powinniśmy użyć innego pojęcia redukowalności?A E O $\mathsf{AUV}$$\mathsf{AEOL}$

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 $\pm k$$k$$\pm1$$\mathsf{AEOL}$$\mathsf{AUV}$

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 1 ≠ y 2 y 2 y 1 A U $\mathsf{AEOL}$$\mathsf{AUV}$$g$$f^{-1}$$g(x,f(x))\ne x$$\mathsf{AUV}$$g$$x$$g(y_1)=g(y_2)$$y_1\ne y_2$$y_2$$y_1$$\mathsf{AUV}$ .

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

Udowodniono, że problemy są równoważne (a zatem kompletne PPAD), patrz sekcja 8 w The Hairy Ball Problem is PPAD-Complete autorstwa Paula W. Goldberga i Alexandrosa Hollendera .

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 .$G$$1$$X$$G$$v\notin X$

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|$$X$$X$

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|$$2^k$$2$$s$$G'=(V',E')$$2^k$$V$$A,B\in V'$$(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=\{a_0,\dots,a_{2^k-1}\}$$B=\{b_0,\dots,b_{2^k-1}\}$$(a_i,b_i)\in E$$i<2^k$

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.$G'$$1$$A\in V'$$G$$A$$A\cap X\ne\varnothing$$1$

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 ($A$$t=|A\cap X|$$0<t\le2^k$$t=2^k=|A|$$A\subseteq X$. Przypomnijmy, że wielokrotność liczby pierwszejpw($\binom{s}{2^k}$$p$ równa się liczbie przeniesień w dodatkub+(a-b)=awykonane w podstawiep. Z wyborukwynika, że ($\binom ab$$b+(a-b)=a$$p$$k$jest nieparzysty. Co więcej, istnieją bijectacje w czasie wielomianowym pomiędzy[0,($\binom{s}{2^k}$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,\binom ab)$$b$$[0,a)$$2^k$$X$$t=2^k$$1$

Dla wzór liczenia przeniesień pokazuje, że ($0<t<2^k$ jest parzysty. Ponownie możemy znaleźć wyraźne dopasowanie nat-elementowe podzbiorówX. Rozszerzamy go na znane źródłaA zapomocą| A∩X| =tpoprzez zastosowanie dopasowania doA∩Xi pozostawienieA∖X nastałym poziomie.$\binom st$$t$$X$$A$$|A\cap X|=t$$A\cap X$$A\smallsetminus X$

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 jest$p$$p$$p$

AUV - : Biorąc pod uwagę ukierunkowany wykres G i wierzchołek, którego równowaga stopni wynosi$p$$G$ , znajdź kolejny taki wierzchołek.${}\not\equiv0\pmod p$

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

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

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 .$p$$p$