Przykłady

Potrzebuję listę pełnych językach. Istnieją dwa takie problemy wymienione w zoo złożoności , a mianowicie:$\Sigma_2^p$

• Minimalny równoważny DNF. Biorąc pod uwagę formułę DNF F i liczbę całkowitą k, czy istnieje formuła DNF równoważna F z k lub mniejszą liczbą literałów?
• Najkrótszy implant. Biorąc pod uwagę wzór F i liczbę całkowitą k, czy istnieje koniunktura k lub mniej literałów implikująca F?

Kolejny podstawowy problem kompletny:$\Sigma_2^p$

• . Biorąc pod uwagę skwantyfikowaną formułę logicznąw postaci, czyważne?$\Sigma_i \text{SAT}$$\varphi$$\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$$\varphi$

Mam jednak nadzieję, że szukam problemu, który korzysta z grafów (np. Problem związany z klikami).

Marcus Schaefer i Chris Umans przeprowadzili miłą ankietę Gareya i Johnsona dotyczącą kompletnych problemów w hierarchii wielomianowej.

Dość nowym rezultatem nieuwzględnionym w pracy Schaefera i Umansa jest 2-KLIKNIĄCE KOLOROWANIE IDEALNYCH WYKRESÓW .

$\Sigma_2^p$

Decydowanie o istnieniu „stabilnej ewolucyjnie strategii” w grze w normalnej formie. Zobacz http://www.cs.duke.edu/~conitzer/ess.pdf .

Konfiguracja to symetryczna gra dla dwóch osób. Strategia stabilna ewolucyjnie jest (losową) strategią, która jest (a) symetryczną równowagą nashową i (b) nie ma dobrych „symetrycznych odchyleń”: w tej równowadze, jeśli jeden gracz może zboczyć do jakiejś strategii i zachować równą użyteczność, wtedy drugi gracz zrobiłby zdecydowanie gorzej, aby następnie odstąpić od tej strategii.