Há algum naturais

Eu sei que o problema quantificado da fórmula booleana para uma fórmula que não contém quantificadores e apenas as variáveis é um exemplo de problema com -complete. No entanto, eu me pergunto se há algum problema natural conhecido como , assim como a Minimização de Circuito é um problema natural (consulte Hierarquia polinomial para obter detalhes)?& Phi; x 1 , ... , x n , y 1 , ... , y n Π P 2 Π P 2 Σ P

$$\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$$\Pi_2^P$$\Sigma_2^P$

Existem muitos problemas naturais completos para , e há uma pesquisa [1] sobre a integridade dos níveis da hierarquia polinomial, contendo muitos desses problemas. O artigo Sobre a complexidade dos problemas de otimização min-max e sua aproximação [2] contém uma boa visão geral dos "problemas min-max" com várias provas de completude. Este último artigo é aberto com a seguinte frase:$\Pi_2^p$

A complexidade computacional dos problemas de otimização da forma min-max é naturalmente caracterizada por , o segundo nível da hierarquia de tempo polinomial.$\Pi_2^p$

Alguns problemas: Aqui estão alguns exemplos, todos , listados na pesquisa mencionada [1].$\Pi_2^p$

• φ ( x , y ) x y φ ( x , y $\forall \exists \text{3SAT}$ : Dada a fórmula 3-SAT , é verdade que para todo existe um tal que seja satisfatório?$\phi(x,y)$$x$$y$$\phi(x,y)$
• NÃO É TUDO EQUAL-$\forall\exists\text{3SAT}$
• MINMAX SAT, CIRCUITO MINMAX, CLIQUE MINMAX
• LISTAR NÚMERO CROMÁTICO
• SATISFIABILIDADE DO GRÁFICO
• CIRCUITO HAMILTONIANO DINÂMICO, O CIRCUITO DIRETO MAIS LONGO
• REACHABILIDADE DE SUCESSO DO TORNEIO
• RESTRIÇÕES SOBRE FUNÇÕES PARCIALMENTE ESPECIFICADAS
• COERÊNCIA DO ARGUMENTO
• EXTENSÃO DE 3 CORES, EXTENSÃO DE 2 CORES
• (FORTE) ARROWING, NÚMERO RAMSEY GERALIZADO
• etc etc.

Referências:

[1] Schaefer, Marcus e Christopher Umans. "Completude na hierarquia do tempo polinomial: um compêndio." Notícias SIGACT 33.3 (2002): 32-49. ( PDF )

[2] Ko, Ker-I. E Chih-Long Lin. "Sobre a complexidade dos problemas de otimização min-max e sua aproximação". Minimax e aplicativos. Springer US, 1995. 219-239. ( PDF )