¿Hay algún problema natural de

Sé que el problema cuantificado de la fórmula booleana para una fórmula donde ϕ no contiene cuantificadores y solo las variables x 1 , ... , x n , y 1 , ... , y n es un ejemplo de un problema Π P 2 completo. Sin embargo, me pregunto si hay algún problema natural conocido por ser Π

$$\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$ -Complete, tal comoCircuito Minimizaciónes un producto naturalΣ P 2 problema -Complete (verjerarquía polinómicapara más detalles)?$\Pi_2^P$$\Sigma_2^P$

$\Pi_2^p$

$\Pi_2^p$

$\Pi_2^p$

• $\forall \exists \text{3SAT}$$\phi(x,y)$$x$$y$$\phi(x,y)$
• $\forall\exists\text{3SAT}$
• MINMAX SAT, CIRCUITO MINMAX, CLIQUE MINMAX
• LISTA DE NÚMERO CROMÁTICO
• GRÁFICO DE SATISFIABILIDAD
• CIRCUITO DINAMICO HAMILTONIANO, EL CIRCUITO DIRECTO MÁS LARGO
• ALCANCE DEL TORNEO DE SUCCINCT
• RESTRICCIONES SOBRE FUNCIONES PARCIALMENTE ESPECIFICADAS
• COHERENCIA DE ARGUMENTO
• EXTENSIÓN DE 3 COLORES, EXTENSIÓN DE 2 COLORES
• FLECHA (FUERTE), NÚMERO RAMSEY GENERALIZADO
• etcétera etcétera.

Referencias

[1] Schaefer, Marcus y Christopher Umans. "Completitud en la jerarquía del tiempo polinomial: un compendio". SIGACT news 33.3 (2002): 32-49. ( PDF )

[2] Ko, Ker-I. Y Chih-Long Lin. "Sobre la complejidad de los problemas de optimización min-max y su aproximación". Minimax y Aplicaciones. Springer US, 1995. 219-239. ( PDF )