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?
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.
Problem wyszukiwania : to samo, ale zarówno jak i zwracają pustą listę lub jeden element.
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
Formalne pytanie : dlaczego zredukować do ? A może powinniśmy użyć innego pojęcia redukowalności?A E O L
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
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 V .
Ostatnie pytanie : czy można jakoś pokonać powyższe przeszkody? Czy można zastosować możliwą zależność od ?x
źródło
Odpowiedzi:
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 .
źródło
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
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
Naszkicuję poniżej argument, że
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| 2k 2 s G′=(V′,E′) 2k V A,B∈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={a0,…,a2k−1} B={b0,…,b2k−1} (ai,bi)∈E i<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.G′ 1 A∈V′ G A A∩X≠∅ 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 ( sA t=|A∩X| 0<t≤2k t=2k=|A| A⊆X . 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+(a−b)=a p k jest 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) 2k X t=2k 1
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ą| A∩X| =tpoprzez zastosowanie dopasowania doA∩Xi pozostawienieA∖X nastałym poziomie.(st) t X A |A∩X|=t A∩X A∖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 jestp p 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
źródło