Let be an alphabet, for instance . Then a language is defined as a subset of . A few examples of languages are:
Given a string and a language , one has the following decision problem: does ?
The class P
The class P is defined as P = . For instance is in P because we saw a dynamic programming algorithm that ran in time polynomial in the size of the input.
The class NP
The class NP is the class of languages that have a short (polynomial in ) certificate for the proof of membership for a string .
Note that P NP, since given a language P there is a polynomial time algorithm that decides membership in the language. Thus for any string , we can think of as a short proof for the membership of in .
The class co-NP
The class co-NP is the class of languages that have a short (polynomial in ) certificate for the proof of non-membership for a string . In other words co-NP where is the complement of .
Some more languages
- Consider the following language . We will see later that is in P. Note that is in NP since if a graph does have edge disjoint paths from to , then a certificate can be the paths.
- The language . Note that it is easy to see that NP.
- The language . Note that if we could argue that if has a solution then it has a solution polynomial in the size of its input, then we could argue that is in NP.
- . Note that is clearly in NP (a perfect matching is a certificate). To see that it is in co-NP, we can use the Konig-Hall’s theorem. Konig-Hall’s theorem says that a bipartite graph has a perfect matching if and only if , where denotes the neighbors of the set in .