In my lecture I saw the problem of $\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\}$

I understand this problem is obviously not in NP as we would need to check all cliques, but if we consider the complement of the problem, (i.e. is the largest clique not of order $k$), wouldn't this be in NP? Because we could simply use non-determinism to guess a clique bigger than $k$ and then check if it indeed makes a clique. My lecturer said however that the problem is not in co-NP but I did not understand the explanation.

  • $\begingroup$ What if the largest clique is smaller than $k$? $\endgroup$ – Pontus Feb 13 '19 at 22:25
  • $\begingroup$ But it does not seem right to claim that the problem is not in NP or coNP, because clearly it is clearly in EXPTIME, and it is unknown if EXPTIME differs from NP and coNP. $\endgroup$ – Pontus Feb 13 '19 at 22:49

The problem "Does the largest clique have a size ≤ k" is in co-NP - if the answer is NO then there is a clique of size > k, and guessing that clique proves that the answer is NO.

But the problem here is "Does the largest clique have a size of exactly k". If the answer is NO then it could be that the largest clique has size k-1 and there are no cliques of size k, k+1, k+2 etc. Sure, you could guess a clique of size k-1 - but that doesn't prove a clique of size k doesn't exist. And you can't guess a clique of size k+1 because no such clique exists.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the clarification. It seems blatantly obvious now. $\endgroup$ – Johnny Pandeleo Feb 13 '19 at 22:59

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.