Jak trudno policzyć liczbę lokalnych optymów dla problemu w PLS?

11

W przypadku wielomianowego problemu wyszukiwania lokalnego wiemy, że musi istnieć co najmniej jedno rozwiązanie (lokalne optimum). Jednak może istnieć wiele innych rozwiązań, jak trudno jest policzyć liczbę rozwiązań problemu z kompletnym PLS? Jestem szczególnie zainteresowany w problemu decyzyjnego: nie wystąpienie tego problemu PLS-complete mają dwa lub więcej rozwiązań?

Czy złożoność zależy od wybranego przez nas problemu pełnego PLS? Jeśli tak, to byłbym szczególnie zainteresowany ważoną 2SAT (jak zdefiniowano w [SY91] i [Rou10]). Wiem, że liczenie satysfakcjonujących rozwiązań dla 2SAT jest # P-ukończone, ale na pierwszy rzut oka wydaje się, że lokalne optymalne ważone 2SAT i rozwiązania dla 2SAT nie mają ze sobą wiele wspólnego.

Wiem także, że dla kuzyna PLS PPAD, [CS02] pokazuje, że zliczanie liczby równowag Nasha jest trudne do #P. Sugeruje to, że podobne problemy PLS, takie jak zliczanie liczby równowag czysto strategicznych w grach z przeciążeniem, byłyby również trudne.

Bibliografia

[CS02] Conitzer, V., i Sandholm, T. (2002). Wyniki złożoności dotyczące równowagi Nasha. IJCAI-03 . cs / 0205074 .

[Rou10] T. Roughgarden. (2010). Równowagi obliczeniowe: perspektywa złożoności obliczeniowej. Teoria ekonomiczna , 42: 193–236.

[SY91] AA Schaeffer i M. Yannakakis. (1991). Proste lokalne problemy wyszukiwania, które są trudne do rozwiązania. SIAM Journal on Computing , 20 (1): 56–87.

cc.complexity-theory counting-complexity gt.game-theory

— Artem Kaznatcheev
źródło

7

Mogę częściowo odpowiedzieć na twoje pytanie: zliczanie lokalnych optymów dla problemu wyszukiwania z kompletnym PLS może być naprawdę trudne.

Po pierwsze, jak zauważa Yoshio, istnieje problem wyszukiwania w PLS, z którym związany jest problem z liczeniem # P-zupełny. (Nie wiemy jednak, czy jest kompletnym PLS.) Niech będzie jakimś problemem związanym z PLS. Następnie zdefiniuj który na wejściu dla , prosi o lokalne optimum dla wejścia względem . Ten problem dziedziczy członkostwo PLS w $P_1$ $P_1$ $P_2$ $P'$ $(x, i)$ $i \in \{1, 2\}$ $x$ $P_i$ $P_1, P_2$ , dziedziczy kompletność PLS dla , a dla problemu liczenia dziedziczy kompletność # P dla . $P_2$ $P_1$

Podobnie można skonstruować (sztuczny) problem z kompletnym PLS, dla którego NP jest kompletny, aby zdecydować, czy istnieje więcej niż jedno lokalne optimum. Podobnie jak w poprzednim argumentu jeden „zszywki razem” a PLS zupełnych problemem , jak poprzednio, z problemem PLS , które na wejściu wzór logiczna , ma więcej niż jeden powiązany lokalnego optimum IFF jest spe. $P_1$ $P_2$ $\psi$ $\psi$

Tego rodzaju konstrukcje są nieco niezadowalające, ponieważ próbujemy zbudować problem wyszukiwania który ma dwie właściwości twardości, ale dziedzina „dzieli się” na dwie części, z których każda może mieć tylko jedną z dwóch właściwości. Poniżej pokażę, w jaki sposób, biorąc pod uwagę problem z wyszukiwaniem w PLS, z którym związany jest problem z liczeniem # P-kompletny i biorąc pod uwagę problem z kompletnym PLS , można zdefiniować problem PLS który jest tak trudny, jak dla obu i wyszukaj w sposób „instancja po instancji”. $Q$ $Q$ $P_1$ $P_2$ $Q$ $P_1$ $P_2$

Mianowicie, pokażemy taki sposób, że rozwiązanie problemu zliczania dla na wejściu skutecznie ogranicza się do rozwiązania problemu zliczania dla na wejściu , a problem z wyszukiwaniem dla na wejściu zmniejsza się do problemu z wyszukiwaniem dla na wprowadź . $Q$ $P_1$ $x$ $Q$ $x$ $P_2$ $x$ $Q$ $x$

Dla uproszczenia prezentacji zakładamy, że są takie, że na dowolnym wejściu długości przestrzeń kandydata na rozwiązanie powiązana z jest powyżej ciągów bitów o długości dla pewnego (ale z różnymi strukturami sąsiedztwa dla ). Niech jest funkcją przydatności związane z . $P_1, P_2$ $x$ $n$ $x$ $y$ $n^c$ $c$ $P_1, P_2$ $F_i(x, y)$ $P_i$

Na wejściu przestrzeń poszukiwań dla jest ponad krotkami gdzie każde jest w , , i $x \in \{0, 1\}^n$ $Q$ $(y^1, y^2, z, b)$ $y^i$ $\{0, 1\}^{n^c}$ $z \in \{0, 1\}^{n^c + 1}$ $b \in \{0, 1\}$ . Jako funkcję sprawności dla definiujemy $F(x, (y^1, y^2, z, b))$ $Q$

jeśli , $F(x, (y^1, y^2, z, b)) := F_1(x, y^1) + F_2(x, y^2)$ $b = 1$

jeśli . $F(x, (y^1, y^2, z, b)) := ||y^1|| + ||z|| + F_2(x, y^2)$ $b = 0$

(To powyżej waga Hamminga.)

Dla struktury sąsiedztwa łączymy każdą krotkę ( ) do wszystkich krotek takie, że $Q$ $(x, (y^1, y^2, z, 1))$ $b = 1$ $(x, ((y')^1, (y')^2, z', 1))$

(A) jest połączone z zgodnie z dla , ORAZ $(x, y^i)$ $(x, (y')^i)$ $P_i$ $i = 1, 2$

(B) różnią się co najwyżej o 1 współrzędną. $z, z'$

W przypadku krotek o wartości łączymy ze wszystkimi krotkami takie że $b = 0$ $(x, (y^1, y^2, z, 0))$ $(x, ((y')^1, (y')^2, z', 0))$

(A ') jest połączone z zgodnie z , ORAZ $(x, y^2)$ $(x, (y')^2)$ $P_2$

(B ') różnią się co najwyżej o 1 współrzędną, podobnie jak . $z, z'$ $y^1, (y')^1$

(Uwaga: krotki z są odłączone od krotek z ) $b = 0$ $b = 1$

To definicja . Okolice mają wielkość wielomianu zgodnie z wymaganiami, więc jest w PLS. $Q$ $Q$

Twierdzenie: Miejscowy optimum wzdłużnych wejścia według są dokładnie dwa następujące zestawy rozłączne: $n$ $x$ $Q$

(1) wszystkie krotki , gdzie to lokalne optimum dla każdego z (i jest dowolne, i ); i, $(x, (y^1, y^2, z,1))$ $(x, y^i)$ $P_i$ $i = 1, 2$ $z$ $b = 1$

(2) wszystkie krotki , gdzie jest lokalnym optimum dla , a gdzie zarówno są all-1, i . $(x, 1^{n^c}, y^2, 1^n, 0))$ $(x, y^2)$ $P_2$ $z, y^1$ $b = 0$

Jeśli zgadzają się, wówczas PLS twardość jest natychmiastowe, ponieważ miejscowego optimum z na wejściu daje lokalnego optimum z (dla tego samego wejścia ), a jest PLS-twardy. $Q$ $(x, (y^1, y^2, z,b))$ $Q$ $x$ $(x, y^2)$ $P_2$ $x$ $P_2$

Z naszego twierdzenia wynika również, że liczba lokalnych optymów dla $N(x)$ $x$ poniżej jest równa , gdzie wynosi liczba lokalnych optima dla poniżej . Teraz jest w zakresie $Q$ $(2^{n^c + 1} N_1(x) + 1) \cdot N_2(x)$ $N_i(x)$ $x$ $P_i$ $N_2(x)$ , więc mamy $[1, 2^{n^c}]$

mod $N_2(x) = N_2(x)$ modmod . $2^{n^c + 1} = (2^{n^c + 1} N_1(x) + 1) \cdot N_2(x)$ $2^{n^c + 1} = N(x)$ $2^{n^c + 1}$

Możemy więc otrzymać biorąc pod uwagę . Następnie możemy również uzyskać , za pomocą prostej algebry: $N_2(x)$ $N(x)$ $N_1(x)$ . Ponieważjest kompletne do obliczenia przez P, podobnie. Zatem # P-zupełne jest zliczanie lokalnych optymów dla(a liczenie dlasprowadza się do liczenia dlaw tej samej instancji). $N_1(x) = \left(\frac{N(x)}{N_2(x)} - 1\right)/2^{n^c + 1}$ $N_1(x)$ $N(x)$ $Q$ $P_1$ $Q$

Nie wiem, jak obniżyć takie połączenie, łącząc twardość PLS z twardością NP, decydując o wyjątkowości lokalnych optymów w sposób „instancja po instancji”.

Jeśli chodzi o to, czy każdy problem wyszukiwania z kompletnym PLS powoduje problem z liczeniem # P, nie wiem tego. Wydaje się, że jest to związane z pytaniem, czy dla każdego problemu decyzyjnego L kompletnego NP i każdego weryfikatora czasu policyjnego dla związany z tym problem liczenia świadków jest # P-kompletny. # P-kompletność obowiązuje we wszystkich szczególnych przypadkach, które ludzie rozważali, i w pewnych względnie łagodnych warunkach, ale ogólnie jest otwarta. Zobacz tę dyskusję . $V(x, y)$ $L$

W przypadku konkretnego, bardziej naturalnego problemu wiadomo, że jest kompletnym PLS, można ustalić kompletność # P do zliczania lokalnych optymów, podając redukcję PLS z powiedzmy Dopasowywanie do która ma pewne specjalne właściwości odpowiednie do zliczania. Może istniejące techniki są wystarczające; Nie próbowałem się przekonać. $Q$ $Q$

— Andy Drucker
źródło

Dziękuję, Andy! To jest bardzo przydatne. Będę musiał przeczytać go jeszcze kilka razy, aby upewnić się, że podążam za wszystkim.

— Artem Kaznatcheev

7

Rozważ maksymalny problem z dopasowaniem w grafach dwustronnych. Rodzina możliwych rozwiązań obejmuje wszystkie dopasowania, a wyszukiwanie lokalne odbywa się poprzez znalezienie ścieżek rozszerzających. Problem należy do PLS, ponieważ ścieżkę rozszerzającą można znaleźć w czasie wielomianowym, jeśli bieżące dopasowanie nie jest maksymalne, a maksymalność można sprawdzić w czasie wielomianowym. Dowolne lokalne optimum jest maksymalnym dopasowaniem (tj. Globalnym optymalnym). Jednak # P-trudne jest obliczenie liczby maksymalnych dopasowań na wykresie dwustronnym.

Ponieważ lokalne optimum można znaleźć w czasie wielomianowym, jest mało prawdopodobne, że problem będzie kompletny z PLS. Obawiam się, że nie jest to zamierzona odpowiedź (twoje pytanie ogranicza się do problemów z kompletnym PLS). Należy jednak zauważyć, że policzenie liczby lokalnych optymów może być trudne, nawet jeśli jedno lokalne optymalne można znaleźć skutecznie.

— Yoshio Okamoto
źródło

Dzięki! Jest to dobra ogólna uwaga na temat ogólnej twardości # P (i dlaczego wspomniałem o 2SAT). Pozostawię pytanie otwarte w nadziei na uzyskanie odpowiedzi na problemy kompletne PLS, a także położę większy nacisk na odróżnienie jednego istniejącego rozwiązania od dwóch lub więcej istniejących rozwiązań (to jest przypadek, który najbardziej mnie interesuje).

— Artem Kaznatcheev

1

Ponieważ unikalność maksymalnego dopasowania można skutecznie sprawdzić, moja odpowiedź nie jest zadowalająca dla pytania, które najbardziej Cię interesuje. Dziękuję.

— Yoshio Okamoto