À quelle classe de complexité appartient ce langage?

Je pensais à quelle classe ce langage appartient: est un graphique, est un nombre naturel et est le nombre chromatique dek k G $L =\{ \langle G,k \rangle \mid G$$k$$k$$G\}$

J'ai pensé à comme (1) "il n'y a pas de coloration des couleurs k-1" et (2) "il y a coloration des couleurs". Maintenant, (1) est coNP et (2) est NP-complet, donc je suppose que ce langage n'est ni en NP ni en coNP, mais je n'ai pas trouvé à quelle classe il appartient. Toute aide sera la bienvenue.$L$$k$

Merci

Il est contenu dans DP: Difference Polynomial-Time , qui est également BH 2 , le deuxième niveau de la hiérarchie booléenne$_2$ . Cette classe est elle-même contenue dans , mais on pense que c'est une classe plus grande.$\Delta^\textrm{P}$

Une langue L est en DP si elle est l'intersection d'une langue L ₁ en NP avec une langue L ₂ en coNP, et donc votre exemple est clairement en DP.

(comme l'a souligné Robin le problème est en DP ...)

... et il est également complet en DP.

En fait, Jörg Rothe a montré que cela vaut même pour k = 4 fixe: Jörg Rothe: complexité exacte de l'exact-quadri-colorabilité. Inf. Processus. Lett. (IPL) 87 (1): 7-12 (2003)