complexity-theorynpnp-completecliqueclique-problem

Is the complement of the language CLIQUE element of NP?


I'm studying about the NP class and one of the slides mentions:

It seems that verifying that something is not present is more difficult than verifying that it is present.
       ______                  _________
Hence, CLIQUE (complement) and SubsetSUM (complement) are not obviously members of NP.

Was it ever proved, whether the complement of CLIQUE is an element of NP?

Also, do you have the proof?


Solution

  • This is an open problem, actually! The complexity class co-NP consists of the complements of all problems in NP. It's unknown whether NP = co-NP right now, and many people suspect the answer is no.

    Just as CLIQUE is NP-complete, the complement of CLIQUE is co-NP-complete. (More generally, the complement of any NP-complete problem is co-NP-complete). There's a theorem that if any co-NP-complete problem is in NP, then co-NP = NP,which would be a huge theoretical breakthrough.

    If you're interested in learning more about this, check out the Wikipedia article on co-NP and look around online for more resources.