Zwięzłe odwzorowanie obwodów grafów

Klasę złożoności PPAD (np. Obliczanie różnych równowag Nasha) można zdefiniować jako zbiór całkowitych problemów z wyszukiwaniem, które można zredukować do ZAKOŃCZENIA LINII :

KONIEC LINII : Biorąc pod uwagę obwody S i P z n bitami wejściowymi i n bitami wyjściowymi takimi, że P (0 ⁿ ) = 0 ⁿ ! = S (0 ⁿ ) , znajdź wejście x w {0,1} ⁿ takie, że P (S (x)) ! = X lub S (P (x)) ! = X ! = 0 ⁿ .

Obwody lub algorytmy, takie jak S i P, domyślnie definiują wykładniczo duży wykres, który jest ujawniany tylko na zasadzie zapytanie po zapytaniu (aby zachować problem w PSPACE !), Np . Praca Papadimitrou .

Nie rozumiem jednak, w jaki sposób zaprojektować obwód, który umożliwia tworzenie dowolnych wykresów (jeśli na wykresie znajduje się systematyczna struktura, znacznie łatwiej jest znaleźć obwód). Na przykład, jak zaprojektować obwód wielomianowy, który reprezentuje wykładniczo długą linię kierunkową, z etykietą „ 0 ” dla wierzchołka źródłowego i losowo przypisanymi etykietami binarnymi do wszystkich innych wierzchołków? Wydaje się, że jest to dorozumiane w dokumentach związanych z PPAD .

Najbliższe wyszukiwanie w sieci to praca Galperina / Widgersona , ale opisany tam obwód przyjmuje dwie etykiety wierzchołków i zwraca odpowiedź logiczną na „Czy te wierzchołki sąsiadują?”

Jak więc zaprojektować obwód wielomianowy wykresu wielkości wykładniczej, który pobiera n- bitowe wejście i wyprowadza n- bitową etykietę odpowiednio swojego poprzednika lub następcy? A nawet, czy ktoś wie o zasobu, który dobrze to wyjaśnia?

Wydaje się, że twoje pytanie brzmi: w jaki sposób reprezentuje się dowolne wykresy (lub nawet dowolne wykresy ścieżek) jako obwód o wielomianu? Odpowiedź brzmi: nie. Liczba różnych wykresów ścieżki z 2 ⁿ wierzchołkami wynosi (2 ⁿ ) !, znacznie więcej niż liczba różnych obwodów z bramkami n ^c (wykładnicza w n ^c log n). Tak więc prawie wszystkie wykresy z tak wieloma wierzchołkami nie mogą być reprezentowane przez zwięzły obwód.

Dlatego, jak wskazujesz, w pewnym sensie można w ten sposób przedstawić tylko wykresy o wysokim stopniu struktury. To sprawia, że ​​klasy złożoności, takie jak PPAD, są interesujące: pomimo znajomości struktury, którą muszą posiadać wykresy wejściowe dla problemu EOL, nie wiemy, jak wykorzystać tę strukturę do skutecznego rozwiązania problemu.

Jeśli źle rozumiem twoje pytanie i naprawdę pytasz: jak stworzyć obwód, który nawet spełnia wymagania wejściowe dla EOL, dla nawet bardzo wysoce ustrukturyzowanego wykresu: wypróbuj wykres ścieżki łączący wierzchołek x (traktowany jako liczba binarnie) do x-1 i x + 1, z końcami zerowymi i 2 ^ n-1. Lub jeśli chcesz czegoś mniej trywialnego, co wydaje się trudniejsze do rozwiązania EOL: niech E i D będą funkcjami szyfrowania i deszyfrowania stałego klucza w twoim ulubionym kryptosystemie, niech sąsiedzi x na wykresie to E (x) i D (x) i niech końce linii będą wynosić 0 i D (0).

Ponieważ większość wykresów na n wierzchołkach jest losowo Kołmogorowa, nie można ich opisać za pomocą obwodu (ani żadnego innego programu), który jest znacznie mniejszy niż sam wykres. (Jeśli nie wiesz, co oznacza Kołmogorow-losowy, możesz zasadniczo przyjąć konkluzję poprzedniego zdania jako jego definicję. Następnie polegaj na tym, że prawie wszystkie ciągi są losowe Kołmogorow.)

Chociaż nie jestem do końca zaznajomiony z cytowanymi pracami, domyślam się, że zawsze mówią o wykresach opisanych obwodami. Innymi słowy, skupiając się na obwodach, zasadniczo ograniczają swoją uwagę do klasy wykresów, które mają zwięzłe obwody (których rozmiar jest logarytmiczny w stosunku do rozmiaru wykresu).