Des exemples de

J'ai besoin d'une liste de langues complètes. Il y a deux de ces problèmes répertoriés dans le Complexity Zoo , à savoir:$\Sigma_2^p$

• DNF équivalent minimum. Étant donné une formule DNF F et un entier k, existe-t-il une formule DNF équivalente à F avec k ou moins d'occurrences de littéraux?
• Implicant le plus court. Étant donné une formule F et un entier k, existe-t-il une conjonction de k ou moins de littéraux qui implique F?

Un autre problème complet de base :$\Sigma_2^p$

• $\Sigma_i \text{SAT}$ . Étant donné une formule booléenne quantifiée de la forme , valide?$\varphi$$\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$$\varphi$

Cependant, je suis à la recherche d'un problème qui utilise des graphiques (par exemple un problème lié à la clique).

Marcus Schaefer et Chris Umans ont une belle étude de Garey-and-Johnson-esque de problèmes complets dans la hiérarchie polynomiale.

Un résultat assez récent non inclus dans le papier Schaefer et Umans est la COLORATION 2-CLIQUE DES GRAPHIQUES PARFAITS .

$\Sigma_2^p$

Décider de l'existence d'une "stratégie évolutive stable" dans un jeu de forme normale. Voir http://www.cs.duke.edu/~conitzer/ess.pdf .

La configuration est un jeu symétrique à 2 joueurs. Une stratégie stable sur le plan de l'évolution est une stratégie (randomisée) qui est (a) un équilibre de Nash symétrique, et (b) il n'y a pas de bons "écarts symétriques": dans cet équilibre, si un joueur peut dévier vers une certaine stratégie et maintenir une utilité égale, alors l'autre joueur ferait strictement pire pour ensuite s'écarter également de cette stratégie.