Czy są jakieś naturalne problemy z

Wiem, że skwantyfikowany problem z formułą logiczną dla formuły gdzie nie zawiera kwantyfikatorów i tylko zmienne jest przykładem . Zastanawiam się jednak, czy są jakieś naturalne problemy, o których wiadomo, że są , tak jak obwodu jest naturalnym (szczegóły w hierarchii wielomianowej )?

$$\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi$$ $\phi$$x_1, \ldots, x_n, y_1, \ldots, y_n$$\Pi_2^P$$\Pi_2^P$$\Sigma_2^P$

Istnieje bardzo wiele naturalnych kompletnych problemów dla , i jest ankieta [1] na temat kompletności poziomów hierarchii wielomianowej, zawierająca wiele takich problemów. Artykuł o złożoności problemów optymalizacji min-max i ich aproksymacji [2] zawiera ładny przegląd „problemów min-max” z kilkoma dowodami kompletności. Ten ostatni artykuł otwiera się następującym zdaniem:$\Pi_2^p$

Złożoność obliczeniowa problemów optymalizacyjnych formy min-max jest naturalnie charakteryzowana przez , drugi poziom hierarchii czasu wielomianowego.$\Pi_2^p$

Niektóre problemy: Oto kilka przykładów, z których wszystkie są kompletne , wymienionych we wspomnianej ankiecie [1].$\Pi_2^p$

• : Biorąc pod uwagę wzór 3-SAT ϕ ( x , y ) , czy to prawda, że ​​dla wszystkich x istnieje y takie, że ϕ ( x , y ) jest zadowalające?$\forall \exists \text{3SAT}$$\phi(x,y)$$x$$y$$\phi(x,y)$
• NOT-ALL-same wymiary $\forall\exists\text{3SAT}$
• MINMAX SAT, MINMAX OBWÓD, MINMAX CLIQUE
• WYKAZ NUMERU CHROMATYCZNEGO
• ZADOWOLENIE WYKRESU
• DYNAMICZNY OBWÓD HAMILTONIJSKI, DŁUŻSZY OBWÓD BEZPOŚREDNI
• SUKCINCYJNA DOSTĘPNOŚĆ TURNIEJU
• OGRANICZENIA CZĘŚCI OKREŚLONYCH CZĘŚCIOWO
• SPÓJNOŚĆ ARGUMENTÓW
• 3-KOLOROWE PRZEDŁUŻENIE, 2-KOLOROWE PRZEDŁUŻENIE
• (MOCNE) STRZAŁKI, Uogólniony numer pamięci RAMSEY
• itd itd.

Bibliografia:

[1] Schaefer, Marcus i Christopher Umans. „Kompletność w hierarchii czasu wielomianowego: Kompendium”. Wiadomości SIGACT 33.3 (2002): 32-49. ( PDF )

[2] Ko, Ker-I. I Chih-Long Lin. „O złożoności problemów optymalizacji min-max i ich przybliżeniu”. Minimax i aplikacje. Springer US, 1995. 219-239. ( PDF )