Is the complement of MAX-CLIQUE in NP? Let $$MAX-CLIQUE = \{\ &lt;G,k&gt;\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$

Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
If $NP=P$, does $MAX-CLIQUE\in P$?


I cannot think of a polynomial verifier for $MAX-CLIQUE$'s complement. There might not be a max clique of size k due to two reasons:

There's a bigger clique than k (and then the verifier will get such clique and verify it).
There's no clique of size k in the graph (and this is cannot be verified in polynomial time).

Regarding the second question: it's known that $MAX-CLIQUE$ is just $NP-HARD$ and not $NP-COMPLETE$. I understand from that that probably $MAX-CLIQUE \notin NP$, therefore even if $P=NP$, so $MAX-CLIQUE \notin NP=P$.
So does it mean that the answer to all the question is simply &quot;no&quot;?
$MAX-CLIQUE \in \mathsf{coNP \Leftrightarrow NP = coNP}$.
The answer is yes: your variant of $MAX-CLIQUE$ is in $\mathsf{P^{NP}}$, since knowing the size of max clique you can solve your problem.


There is no polynomial verifier (if $\mathsf{NP \neq P^{NP}}$) for this problem, because it is not in $\mathsf{NP}$.

Classic $MAX-CLIQUE$ which only asks if there is a clique of size at least $k$ is $\mathsf{NP}$-complete. But if $\mathsf{P = NP}$ you can ask a machine if there is a clique of size $|V|, |V| - 1, |V|-2...$ until the answer is "YES" to find max clique. Of course, you can use binary search instead of linear. 

So, $\mathsf{P = NP}\Leftrightarrow MAX-CLIQUE\in \mathsf{P}$.