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 n ) = 0 n ! = S (0 n ) , znajdź wejście x w {0,1} n takie, że P (S (x)) ! = X lub S (P (x)) ! = X ! = 0 n .
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?
źródło