# Is the complement of MAX-CLIQUE in NP?

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"?

• I. What do you mean by complement? A subgraph that doesn't contain max clique? II. No, $\mathsf{P = NP \Leftrightarrow P = PH}$. Since $MAX-CLIQUE \in \mathsf{PH}$ it will be in $\mathsf{P}$ also. – rus9384 Jul 3 '17 at 17:55
• By $MAX-CLIQUE$'s complement I mean $\overline{MAX-CLIQUE}$ – iTayb Jul 3 '17 at 18:05
• So, you mean decision variant $MAX-CLIQUE$? Otherwise I have a difficulty in understanding this. There is an $INDEPENDENT-SET$ problem which may seem to be a complement to $MAX-CLIQUE$ but it is not. – rus9384 Jul 3 '17 at 18:07
• What is MAX-CLIQUE for you? Can you formally state it? – Yuval Filmus Jul 3 '17 at 18:08
• Of course, sorry. I thought the definition of MAX-CLIQUE is the same everywhere. I've edited the question accordingly. – iTayb Jul 3 '17 at 18:12

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}$.

• There is no polynomial verifier - why is that. – Eugene Jul 3 '17 at 21:07
• @Eugene, this problem is clearly $\mathsf{NP\cup coNP}$-hard: you can solve both $MAX-CLIQUE$ and $\overline{MAX-CLIQUE}$ with it. Also, it can be that $\mathsf{NP = coNP}$. Then polynomial verifier exists. – rus9384 Jul 3 '17 at 21:47
• I think there is dubious term usage $MAX-CLIQUE$. OPs definition might have a verifier if $\mathcal{NP} = \mathcal{coNP}$. Anyway, everything is clear to me now. – Eugene Jul 3 '17 at 22:03
• That's what I wrote. Maybe you haven't seen it, as I edited comment. But same is written in the answer: see "if $\mathsf{NP\neq P^{NP}}"$. – rus9384 Jul 3 '17 at 22:04