# Is the complement of MAX-CLIQUE in NP?

Let $$MAX-CLIQUE = \{\ \ |\ 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