The class "co-NP" is the class of all languages L for which the complement Lc∈NP. That is, co-NP is the class of all languages L for which a non deterministic Turing Machine exists that accepts a word w iff w∉L. In yet other words,
co-NP = {Lc | L∈NP}
If you know any problem in NP, you know a problem in co-NP:
- SAT∈NP (satisfiability of boolean formulae: given a boolean formula f, does there exist an assignment to the variables appearing in f for which f is true? So co-SAT∈co-NP: Non-satisfiability, or the language of all formulae f for which no satisfying assignment exists. Note that this is not strictly true: In fact, words w which do not constitute a well formed formula are excluded from SAT, so they should also be included in co-SAT. We ignore this wrinkle, as clearly these words w can be identified in polynomial time and disposed with as we wish.
- 3-coloring∈NP: determining whether a graph can be coloured using 3 colours is easy in NP. Guess a 3-colouring of the graphs' vertices, and verify it in polynomial time. So co-3-coloring∈co-NP: This is determining that a graph cannot be 3-colored. Again, co-3-coloring would presumably include all cases of inputs which are invalid by virtue of not describing a graph; as usual in the literature, we tend to ignore these, as the trivial polynomial algorithm recognizes them.
Both of the original problems are, in fact,
NP-complete problems. And it turns out that this is enough to make their complements co-NP-complete. The structures are such obvious
mirror images that not much is usually made of co-NP-completeness, though.
We can also expand the more structural definition which appears in my writeup for NP:
A language L∈co-NP iff there exists a boolean function f(x,y) with |y| = |x|O(1) (the length of y is polynomial in the length of x) such that
- f∈P: f is computable in polynomial time (on a deterministic Turing machine); since |y|=|x|O(1), this means that f is computable in time polynomial in |x|.
- For any x, x∈L iff ∀y.~f(x,y): It doesn't matter with which y we pick, we can't have f(x,y)=TRUE.
Note that there is no class co-P. This is because P=co-P: If L is a language computable in polynomial time by a deterministic Turing machine M, then Lc is computable in polynomial time by the deterministic Turing machine M' which first runs M on the input, and then reverses its answer by translating "TRUE" to "FALSE" and vice versa. In other words, L∈P iff Lc∈P. This is true for any deterministic complexity class.
As an immediate consequence, if P=NP then P=co-NP: For any language L,
L∈NP iff L∈P (because we assume P=NP) iff Lc∈P iff Lc∈NP (because we assume P=NP) iff L∈co-NP.
However,
for all we know it could be that P≠NP and still NP=co-NP. So, while a proof that NP=co-NP may not win you a
Millennium prize (it probably should, though!), it will definitely win you
fame and fortune.
Certain problems are known to be in the class Δ1=NP∩co-NP (the polynomial hierarchy -- if someone writes it up -- explains this notation). The most important one is FACTOR: (n,m)∈FACTOR iff n has a factor x<m. This is the decision problem associated with factoring, and it's fairly easy to see that a polynomial algorithm deciding FACTOR can easily be adapted into a polynomial algorithm for finding all factors of any number n. Now, FACTOR∈NP: just guess a factor of n which happens to be smaller than m. It turns out also that FACTOR∈co-NP, so FACTOR∈Δ1.
Not too much is known about the class Δ1. Thanks to its construction, we know that co-Δ1=Δ1 (a problem is in co-NP and in NP iff it's in NP and in co-NP, but that's not very interesting). Similarly (and equally boring), co-P=P (this is true for any deterministic complexity class). We know that this chain of inclusions holds:
NP co-NP
\ /
\ /
Δ1
|
|
P
but we don't know if any of the inclusions is strict or not.
Open question #2: Does P=Δ1?
Open problem #3: Are there any complete problems for Δ1?
"Hint" for all 3 problems: Most people would answer "NO" to all. Bear in mind, however, that nobody knows.