¿A qué clase de complejidad pertenece este lenguaje?

Estaba pensando a qué clase pertenece este lenguaje: es un gráfico, es un número natural es el número cromático de$L =\{ \langle G,k \rangle \mid G$$k$$k$$G\}$

Pensé en como (1) "no hay coloración de k-1 colores" y (2) "hay coloración de colores". Ahora, (1) es coNP y (2) tiene NP completo, así que supongo que este lenguaje no está en NP ni en coNP, pero no encontré a qué clase pertenece. Cualquier ayuda será bienvenida.$L$$k$

Gracias

Está contenido en DP: Difference Polynomial-Time , que también es BH , el segundo nivel de la jerarquía booleana$_2$ . Esta clase está contenida en , pero se cree que es una clase más grande.$\Delta^\textrm{P}$

Un lenguaje L está en DP si es la intersección de un idioma L ₁ en NP con un idioma L ₂ en coNP, por lo que su ejemplo está claramente en DP.

(como señaló Robin, el problema está en DP ...)

... y también es DP-complete.

De hecho, Jörg Rothe ha demostrado que esto incluso es válido para k = 4 fijo: Jörg Rothe: Complejidad exacta de la capacidad de coloración exacta de cuatro. Inf. Proceso. Letón. (IPL) 87 (1): 7-12 (2003)