# Feb 20. P, NP and co-NP

Languages

Let $\Sigma$ be an alphabet, for instance $\Sigma = \{0,1\}$. Then a language $L$ is defined as a subset of $\Sigma^*$. A few examples of languages are:

• $PRIMES = \{ n \mid n \text{ is a prime number} \}$
• $HAMILTON = \{ G \mid G \text{ has a hamiltonian cycle} \}$
• $EDIT_d = \{ (x, y) \mid \text{ edit distance of x, y} \le d\}$
• $SAT = \{ \phi \mid \phi \text{ is a boolean formula that is satisfiable}\}$

Given a string $x$ and a language $L$, one has the following decision problem: does $x \in L$?

The class P

The class P is defined as P = $\{L \mid x\in L\text{ can be decided in time polynomial in } |x|\}$. For instance $EDIT_d$ 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 $L$ that have a short (polynomial in $|x|$) certificate $y$ for the proof of membership for a string $x \in L$.

Note that P $\subseteq$ NP, since given a language $L \in$ P there is a polynomial time algorithm $A$ that decides membership in the language. Thus for any string $x$, we can think of $A(x)$ as a short proof for the membership of $x$ in $L$.

The class co-NP

The class co-NP is the class of languages $L$ that have a short (polynomial in $|x|$) certificate $y$ for the proof of non-membership for a string $x \notin L$. In other words co-NP $= \{ \bar{L} \mid L \in \text{NP}\}$ where $\bar{L}$ is the complement of $L$.

Some more languages

1. Consider the following language $FLOW = \{ G, s, t, k \mid \exists k \text{ edge disjoint paths from } s \text{ to } t \text{ in } G\}$. We will see later that $FLOW$ is in P. Note that $FLOW$ is in NP since if a graph does have $k$ edge disjoint paths from $s$ to $t$, then a certificate can be the $k$ paths.
2. The language $PERFECTMATCHING = \{ G \mid G \text{ has a perfect matching } \}$. Note that it is easy to see that $PERFECTMATCHING \in$ NP.
3. The language $LP = \{ (A, b) \mid \exists x : Ax \le b\}$. Note that if we could argue that if $Ax \le b$ has a solution then it has a solution polynomial in the size of its input, then we could argue that $LP$ is in NP.
4. $BIPARTITEMATCHING = \{ G \mid G \text{ is a bipartite graph that has a perfect matching }\}$. Note that $G$ 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 $G$ has a perfect matching if and only if $\forall X \subseteq A, |N(X)| \ge |X|$, where $N(X)$ denotes the neighbors of the set $X$ in $G$.