Perché Exact-Clique non è in co-NP?

Question

Nella mia lezione ho visto il problema di$ text {Exact-cLique} = { langle g, k rangle: text {la più grande clique in $ g $ è dell'ordine $ k $} } $

Capisco che questo problema non è ovviamente in NP in quanto avremmo bisogno di controllare tutte le cricche, ma se consideriamo il complemento del problema (cioè è la più grande cricca non di ordine $ k $), non sarebbe questo in NP? Perché potremmo semplicemente usare il non determinismo per indovinare una cricca più grande di $ k $ E poi controlla se fa davvero una cricca. Il mio docente ha detto tuttavia che il problema non è in CO-NP ma non ho capito la spiegazione.