Let $$MAX-CLIQUE = \{\ <G,k>\ |\ 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 "no"?