Łatwy problem decyzyjny, trudny problem wyszukiwania

Decyzja, czy istnieje równowaga Nasha, jest łatwa (zawsze tak jest); jednak znalezienie takiego uważa się za trudne (jest to PPAD-Complete).

Jakie są inne przykłady problemów, w których wersja decyzyjna jest łatwa, ale wersja wyszukiwania jest stosunkowo trudna (w porównaniu z wersją decyzyjną)?

Byłbym szczególnie zainteresowany problemami, w których wersja decyzyjna nie jest trywialna (w przeciwieństwie do równowagi Nasha).

Biorąc pod uwagę liczbę całkowitą, czy ma ona nietrywialny czynnik? -> Nietrywialnie w P.

Biorąc pod uwagę liczbę całkowitą, znajdź nietrywialny czynnik, jeśli taki istnieje -> Nie wiadomo, że jest w FP.

Oto inny przykład: Biorąc pod uwagę wykres sześcienny G i cykl hamiltonowski H w G, znajdź inny cykl hamiltonowski w G. Taki cykl istnieje (według twierdzenia Smitha), ale o ile wiem, jest otwarte, czy może być obliczone w czasie wielomianowym.

Jeśli dasz temu samemu „swobodę”, jaką robisz dla równowagi Nasha, to:

• Faktoryzacja liczb całkowitych, gdzie problemem decyzyjnym jest „Czy istnieje faktoryzowana reprezentacja tej liczby całkowitej?” (trywialnie, tak), a problemem wyszukiwania jest wydrukowanie go

Można sobie wyobrazić, że szereg problemów z siecią może mieć ten sam rodzaj hojnej tolerancji dla zdefiniowania problemu decyzyjnego:

• Problem najkrótszego wektora (SVP) - zdecyduj, czy jest najkrótszy wektor, czy go znaleźć
• Problem najbliższego wektora (CVP) - zdecyduj, czy jest najbliższy wektor vs go znaleźć

Oczywiście są to wszystkie przypadki, w których wspomniana wersja decyzyjna nie jest bardzo interesująca (ponieważ tak jest w przypadku trywialnym). Jeden problem, który nie jest tak trywialny :

• Płaski wykres kolorystyka dla k ≥ $k$$k \ge 4$

Problem decyzyjny na 4-kolorystyce płaskiego wykresu znajduje się w P. Ale uzyskanie leksykograficznie pierwszego takiego rozwiązania jest NP-twarde ( Khuller / Vazirani ).

Zwróć uwagę, że właściwość, którą naprawdę interesujesz, to zdolność do samoodwracalności (a raczej nie-samodopuszczalności). W problemie kolorowania wykresów płaskich istotną kwestią jest to, że metoda samoczynnego zmniejszenia ogólnego przypadku kolorowności zniszczy płaskość na wykresie.$k$

Niech , losowy wykres na 1 , ... , n , przy czym każda krawędź jest niezależnie występuje z prawdopodobieństwem 1 / 2 . Wybrać n 1 / 3 wierzchołki G równomiernie losowo i dodać wszystkie krawędzie między nimi; wywołać otrzymanego wykresu H . Następnie H posiada klika wielkości n 1 / 3 .$G=G(n,1/2)$$1,\ldots,n$$1/2$$n^{1/3}$$G$$H$$H$$n^{1/3}$

Problem wyszukiwania: znajdź klikę o rozmiarze co najmniej .$10\log n$

$a_1,a_2,a_3,...,,a_n$$\sum_1^n{a_i} \lt 2^n -1$$I, J$${1,2,..., n}$$\sum_{i\in I} a_i=\sum_{j \in J} a_j$$I$$J$

Równość sum częściowych (wersja szuflady)

$n$$n$$2n$$n$$n$), ale nie jest znany bezwarunkowy algorytm deterministyczny wielomianowy. Powiązane prace zostały ostatnio wykonane w projekcie Polymath4 ; Stanowisko blogu Tao na temat projektu jest dobrym podsumowaniem.

Ryzykując, że będę nieco nie na temat, dam prosty i naturalny przykład odpowiedzi teorii C : cykle Eulera i algorytmy rozproszone.

Problem decyzyjny nie jest całkowicie trywialny w tym sensie, że istnieją zarówno wykresy Eulera, jak i nie-Eulera.

Istnieje jednak szybki i prosty algorytm rozproszony, który rozwiązuje problem decyzyjny (w tym sensie, że w przypadku wystąpienia „tak” wszystkie węzły wyprowadzają „1”, aw przypadku braku wystąpienia co najmniej jeden węzeł wyprowadza „0”): każdy węzeł po prostu sprawdza parzystość własnego stopnia i odpowiednio 0 lub 1.

$\Omega(n)$$O(n)$

$O(1)$$\Theta(n)$

Edycja: Zakłada to domyślnie, że wykres jest połączony (lub równoważnie, że chcemy znaleźć cykl Eulera w każdym podłączonym składniku).

Znalezienie partycji Tverberg ma nieznaną złożoność:

$x_1,x_2,\dots, x_m$$R^d$$m \ge (r-1)(d+1)+1$$S_1,S_2,\dots, S_r$${1,2,\dots,m}$$\cap _{j=1}^r \text{conv} (x_i: i \in S_j) \ne \emptyset$

Podobnie jak w przypadku równowag Nasha, podział jest gwarantowany przez twierdzenie, ale nie wiadomo, czy istnieje algorytm politime dla jego znalezienia.

Gil Kalai napisał wspaniałą serię postów na ten temat: Jeden , dwa i trzy .

We wszystkich powyższych przykładach problem decyzyjny występuje w P, a problem wyszukiwania nie jest znany w P, ale nie jest również trudny do NP. Chcę podkreślić, że istnieje problem z wyszukiwaniem trudnym dla NP, którego wersja decyzyjna jest łatwa.

Rozważ ogólny problem satysfakcji dla danych relacji $R_1,\ldots,R_k$$\{0,1\}$

$R_1,\ldots,R_k$$R = \{(1,0,0),(0,1,0),(1,1,1)\}$$k = 1$). Gdy problem satysfakcji zostanie rozwiązany w czasie wielomianowym, pytanie, czy istnieje leksykograficznie minimalne zadowalające zadanie, jest trywialne.

Patrz wniosek 13 i następujący po nim przykład w powyższym artykule (przynajmniej w tej wersji on-line).

• $k$$k$
• Wersja do wyszukiwania to NP- twarda: Znajdowanie chromatycznej liczby wykresów bez indukowanej ścieżki z pięcioma wierzchołkami; z powodu tego papieru .

$e$$e (a + b, c + d) = e (a c) e (a d) e (b c) e (b d)$$e$

$e$$(g, h, g^a, h^b)$$a = b$$e (g, h^b) = e (h, g^a)$

Takie grupy są również uogólnione na „grupy luk”.

Myślę, że Planar Perfect Matching nie trafił na tę listę.

• $\mathsf{NC}$
• $\mathsf{NC}$

Zwiększmy nieco złożoność.

Wiele problemów decyzyjnych dotyczących systemów dodawania wektorów (VAS) jest pełnych EXPSPACE, ale może wymagać znacznie większych świadków. Na przykład decyzja, czy język VAS jest prawidłowy, jest EXPSPACE-complete (np. Blockelet i Schmitz, 2011 ), ale najmniejszy równoważny automat stanu skończonego może być wielkości Ackermanniana ( Valk i Vidal-Naquet, 1981 ). Wyjaśnieniem tej ogromnej luki za to, że istnieje znacznie mniejsze świadków non -regularity.