# Why is EXACT-CLIQUE not in co-NP?

In my lecture I saw the problem of $$\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in G is of order k}\}$$

I understand this problem is obviously not in NP as we would need to check all cliques, but if we consider the complement of the problem, (i.e. is the largest clique not of order $$k$$), wouldn't this be in NP? Because we could simply use non-determinism to guess a clique bigger than $$k$$ and then check if it indeed makes a clique. My lecturer said however that the problem is not in co-NP but I did not understand the explanation.

• What if the largest clique is smaller than $k$? – Pontus Feb 13 '19 at 22:25
• But it does not seem right to claim that the problem is not in NP or coNP, because clearly it is clearly in EXPTIME, and it is unknown if EXPTIME differs from NP and coNP. – Pontus Feb 13 '19 at 22:49