CODEWITHSUNDEEP
complexity-theorynpnp-completecliqueclique-problem
Kevin Van Ryckegem
Kevin Van Ryckegem

Reputation: 1945

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?

Upvotes: 1

Views: 3022

Answers (2)

Captain Segfault
Captain Segfault

Reputation: 1726

The general intuition here: it's easy to prove a graph contains an N-clique: just show me the clique. It's hard to prove a graph that doesn't have an N-clique in fact doesn't have an N-clique. What property of the graph are you going to exploit to do that?

Sure, for some families of graphs you can -- for example, graphs with sufficiently few edges can't possibly have such a clique. It's entirely possible that all graphs can have similar proofs built around them, although it'd be surprising -- almost as surprising as P=NP.

This is why the complement of languages in NP are not, in general, obviously in NP -- in fact, we have the term "co-NP" (as in "the complement is in NP") to refer to languages like !CLIQUE.

One common approach to make progress in complexity theory, where we haven't made progress against the hard questions, is to show that some specific hard-to-prove result would imply something surprising. Showing that NP=co-NP is a common target of these proofs -- for example, any hard problem in both NP and co-NP probably isn't complete for either, because if it were it is complete for both and thus both are equal, so somehow you have those crazy general graph proofs.

This even generalizes -- you can start talking about what happens if your NTMs (or certificate checkers) have an oracle for an NP complete language like CLIQUE. Obviously both CLIQUE and !CLIQUE is in P^CLIQUE, but now there are (probably) new languages in NP^CLIQUE and co-NP^CLIQUE, and you can keep going further until you have an entire hierarchy of complexity classes -- the "polynomial hierarchy". This hierarchy intuitively goes on forever, but may well collapse at some point or even not exist at all (if P=NP).

The polynomial hierarchy makes this general argument technique more powerful -- showing that some result would make the polynomial hierarchy collapse to the 2nd or 3rd level would make that result pretty surprising. Even showing it collapses at all would be somewhat surprising.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373082

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.

Upvotes: 2

Related Questions