Pourquoi le clique exacte n'est-il pas en CO-NP?

Question

Dans ma conférence, j'ai vu le problème de$ text {exact-clique} = { langle g, k marche

Je comprends que ce problème n'est évidemment pas en NP car nous aurions besoin de vérifier toutes les cliques, mais si nous considérons le complément du problème, (c'est-à-dire la plus grande clique qui n'est pas de l'ordre $ k $), ne serait-ce pas en NP? Parce que nous pouvions simplement utiliser le non-déterminisme pour deviner une clique plus grande que $ k $ Et puis vérifiez si cela fait en effet une clique. Mon conférencier a cependant dit que le problème n'était pas en CO-NP, mais je n'ai pas compris l'explication.