Do jakiej klasy złożoności należy ten język?

Zastanawiałem się, do której klasy należy ten język: jest wykresem, jest liczbą naturalną, a jest liczbą chromatyczną$L =\{ \langle G,k \rangle \mid G$$k$$k$$G\}$

Myślałem o jako (1) „nie ma zabarwienia kolorów k-1” i (2) „jest zabarwienie kolorów ”. Teraz (1) to coNP, a (2) jest NP-zupełny, więc zakładam, że ten język nie jest ani w NP, ani w coNP, ale nie znalazłem do której klasy należy. Każda pomoc będzie mile widziana.$L$$k$

Dzięki

Jest on zawarty w DP: Difference Polynomial-Time , który jest również BH , drugim poziomem logicznej hierarchii$_2$ . Ta klasa jest zawarta w , ale uważa się, że jest to klasa większa.$\Delta^\textrm{P}$

Język L jest w DP, jeśli jest to przecięcie języka L ₁ w NP z językiem L ₂ w coNP, więc twój przykład jest wyraźnie w DP.

(jak zauważył Robin, problem dotyczy DP ...)

... i jest również kompletny DP.

W rzeczywistości Jörg Rothe wykazał, że dotyczy to nawet ustalonego k = 4: Jörg Rothe: Dokładnie złożona dokładność czterech kolorów. Inf. Proces. Łotysz. (IPL) 87 (1): 7-12 (2003)