Is the complement of MAX-CLIQUE in NP?

Question

Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$

1. Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
2. 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:

1. There's a bigger clique than k (and then the verifier will get such clique and verify it).
2. 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 "no"?

Answer 1

1. $MAX-CLIQUE \in \mathsf{coNP \Leftrightarrow NP = coNP}$.
2. 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}$.