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 )?

ψ = \forall x_{1} \dots \forall x_{n} \exists y_{1} \dots \exists y_{n} ϕ

$\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi$

ϕ

$\phi$

x_{1}, \dots, x_{n}, y_{1}, \dots, y_{n}

$x_1, \ldots, x_n, y_1, \ldots, y_n$

Π_{2}^{P}

$\Pi_2^P$

Π_{2}^{P}

$\Pi_2^P$

Σ_{2}^{P}

$\Sigma_2^P$

complexity-classes

— miernik
źródło

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 , czy to prawda, że dla wszystkich istnieje takie, że 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 )

— Pål GD
źródło