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.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s