¿Ejemplos de problemas completos de

Necesito una lista de idiomas completos. Hay dos de estos problemas enumerados en el Complejo Zoo , a saber:$\Sigma_2^p$

• Mínimo equivalente DNF. Dada una fórmula DNF F y un entero k, ¿hay una fórmula DNF equivalente a F con k o menos ocurrencias de literales?
• El implicante más corto. Dada una fórmula F y un entero k, ¿hay una conjunción de k o menos literales que implique F?

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

• . Dada una fórmula booleana cuantificada φ de la forma φ = ∃ → u ∀ → $\Sigma_i \text{SAT}$$\varphi$ , ¿es φ válido?$\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$$\varphi$

Sin embargo, espero encontrar un problema que utilice gráficos (por ejemplo, un problema relacionado con la camarilla).

Marcus Schaefer y Chris Umans tienen una buena encuesta de Garey y Johnson-esque de problemas completos en la jerarquía polinómica.

Un resultado bastante reciente que no se incluye en el documento de Schaefer y Umans es 2-CLIQUE COLORING OF PERFECT GRAFHS .

Ver David Defossez, Complejidad de gráficos sin agujeros de colores de camarilla . J. Graph Theory 62, 2 (octubre de 2009), 139-156, y algunas mejoras recientes (2013): Hélio B. Macêdo Filho, Raphael CS Machado, Celina MH de Figueiredo, Complejidad jerárquica de gráficos de 2 cuerdas de color débilmente cordal. y gráficos perfectos que tienen camarillas de tamaño de al menos 3 (el problema sigue siendo$\Sigma_2^p$-completar para gráficos débilmente cordales, y para gráficos perfectos que tengan camarillas de tamaño de al menos 3).

Decidir la existencia de una "estrategia evolutivamente estable" en un juego de forma normal. Ver http://www.cs.duke.edu/~conitzer/ess.pdf .

La configuración es un juego simétrico para 2 jugadores. Una estrategia evolutivamente estable es una estrategia (aleatoria) que es (a) un equilibrio simétrico nash, y (b) no hay buenas "desviaciones simétricas": en este equilibrio, si un jugador puede desviarse de alguna estrategia y mantener la misma utilidad, entonces el otro jugador haría lo peor para desviarse también de esta estrategia.