1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rus9384 Jul 3 '17 at 17:55
  • $\begingroup$ By $MAX-CLIQUE$'s complement I mean $\overline{MAX-CLIQUE}$ $\endgroup$ – iTayb Jul 3 '17 at 18:05
  • $\begingroup$ 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. $\endgroup$ – rus9384 Jul 3 '17 at 18:07
  • $\begingroup$ What is MAX-CLIQUE for you? Can you formally state it? $\endgroup$ – Yuval Filmus Jul 3 '17 at 18:08
  • $\begingroup$ Of course, sorry. I thought the definition of MAX-CLIQUE is the same everywhere. I've edited the question accordingly. $\endgroup$ – iTayb Jul 3 '17 at 18:12
2
$\begingroup$
  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}$.

$\endgroup$
  • $\begingroup$ There is no polynomial verifier - why is that. $\endgroup$ – Eugene Jul 3 '17 at 21:07
  • $\begingroup$ @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. $\endgroup$ – rus9384 Jul 3 '17 at 21:47
  • $\begingroup$ 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. $\endgroup$ – Eugene Jul 3 '17 at 22:03
  • $\begingroup$ 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}}"$. $\endgroup$ – rus9384 Jul 3 '17 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.