Existe-t-il des problèmes naturels

Je sais que le problème de formule booléenne quantifiée pour une formule où ne contient aucun quantificateur et seulement les variables est un exemple d'un -complet. Cependant, je me demande s'il existe des problèmes naturels connus pour être -complets, tout comme la minimisation des circuits est un problème naturel -complete (voir Hiérarchie polynomiale pour plus de détails)?

ψ = \forall X_{1} \dots \forall X_{n} \exists y_{1} \dots \exists y_{n} ϕ

$\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi$

ϕ

$\phi$

x_{1}, \dots, x_{n}, y_{1}, \dots, y_{n}

$x_1, \ldots, x_n, y_1, \ldots, y_n$

Π_{2}^{P}

$\Pi_2^P$

Π_{2}^{P}

$\Pi_2^P$

Σ_{2}^{P}

$\Sigma_2^P$

complexity-classes jauge
la source

Réponses:

Il existe de très nombreux problèmes naturels complets pour , et il existe une enquête [1] sur l'exhaustivité des niveaux de la hiérarchie polynomiale, contenant de nombreux problèmes de ce type. L'article Sur la complexité des problèmes d'optimisation min-max et leur approximation [2] contient une belle vue d'ensemble des "problèmes min-max" avec plusieurs preuves d'exhaustivité. Ce dernier document est ouvert par la phrase suivante: $\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, MINMAX CIRCUIT, MINMAX CLIQUE
LISTE NUMÉRO CHROMATIQUE
GRAPHISME DE SATISFIABILITÉ
CIRCUIT HAMILTONIEN DYNAMIQUE, CIRCUIT DIRIGÉ LE PLUS LONG
CAPACITÉ DE RÉUSSITE DU TOURNOI
CONTRAINTES SUR DES FONCTIONS PARTIELLEMENT SPÉCIFIÉES
COHÉRENCE D'ARGUMENT
EXTENSION 3 COULEURS, EXTENSION 2 COULEURS
(FORT) FLÈCHE, NUMÉRO DE RAMSEY GÉNÉRALISÉ
etc.

Références:

[1] Schaefer, Marcus et Christopher Umans. "Complétude dans la hiérarchie polynomiale-temps: Un recueil." SIGACT news 33.3 (2002): 32-49. ( PDF )

[2] Ko, Ker-I. Et Chih-Long Lin. "Sur la complexité des problèmes d'optimisation min-max et leur approximation." Minimax et applications. Springer US, 1995. 219-239. ( PDF )

Pål GD
la source