Exemplos de

Eu preciso de uma lista de idiomas completos. Existem dois desses problemas listados no Complexity Zoo , a saber:$\Sigma_2^p$

• DNF equivalente mínimo. Dada uma fórmula DNF F e um número inteiro k, existe uma fórmula DNF equivalente a F com k ou menos ocorrências de literais?
• Menor implicante. Dada uma fórmula F e um número inteiro k, existe uma conjunção de k ou menos literais que implica F?

Outro problema básico completo:$\Sigma_2^p$

• $\Sigma_i \text{SAT}$ . Dada uma fórmula booleana quantificada da forma , é$\varphi$$\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$ válido?$\varphi$

No entanto, espero que esteja procurando um problema que faça uso de gráficos (por exemplo, um problema relacionado ao clique).

Marcus Schaefer e Chris Umans têm uma ótima pesquisa de Garey-Johnson-esque de problemas completos na hierarquia polinomial.

Um resultado bastante recente, não incluído no artigo de Schaefer e Umans, é 2-CLIQUE COLORING OF PERFECT GRAPHS .

$\Sigma_2^p$

Decidir a existência de uma "estratégia evolutivamente estável" em um jogo de forma normal. Veja http://www.cs.duke.edu/~conitzer/ess.pdf .

A configuração é um jogo simétrico para 2 jogadores. Uma estratégia evolutivamente estável é uma estratégia (randomizada) que é (a) um equilíbrio simétrico nash e (b) não há bons "desvios simétricos": nesse equilíbrio, se um jogador puder se desviar de alguma estratégia e manter a mesma utilidade, então o outro jogador faria estritamente pior para desviar também para essa estratégia.