11.2. NP

Say that an evidence checker runs in polynomial time if the check takes polynomial time. We don't care how much time is used to find the evidence — that is done by somebody else.

NP is a class of decision problems, defined as follows.

Definition. A language L is in class NP if there exists an evidence checker V so that

  1. V(x, e) runs in polynomial time in the lengths of its inputs, x and e.

  2. (V is reasonable.)
    There is an integer k so that,
      for every integer n
      and every string x of length n
        if xL then
          there exists a string e whose
          length is ≤ nk so that
            V(x, e) returns true.

  3. (V is not gullible.)
    If x ∉ L then
     for every e (no matter how long),
      V(x, e) = false.


Examples of problems in NP


Composite numbers

An integer k is composite if k > 1 and there are two integers i and j, where 1 < i, j < k, so that k = ij.

Define COMPOSITE to be the set of composite numbers. As a decision problem, it is:

Input. A positive integer k.

Question. Is k composite?

Theorem. COMPOSITE is in NP.

Proof. All we need to do is find a polynomial time evidence checker for COMPOSITE. Here is one.

Evidence: a pair of integers i and j.

Checker(k, e): Accept evidence e = (i, j) if

  1. k > 1.
  2. e has the correct form (i, j)
  3. 1 < i < k and 1 < j < k
  4. k = ij.
Otherwise, reject evidence e.

Notice that

  1. Correct evidence is only about twice the length of k, so it is short.

  2. If k is composite then there exists correct evidence (i, j) so that Check(k, (i, j)) accepts.

  3. If k is not composite then Check(k, e) rejects for every possible evidence e. ◊


The vertex cover problem

An undirected graph is given by a set of vertices and a set of edges. Each edge is a set of exactly two vertices.

Suppose that G is an undirected graph. A vertex cover of G is a set S of vertices so that every edge is incident on at least one vertex of G.

For example, suppose that undirected graph G has vertices

{1, 2, 3, 4, 5, 6, 7, 8, 9}

and its edges are

{1, 2}, {1, 4},
{1, 6}, {1, 8},
{2, 3}, {3, 4},
{4, 5}, {5, 6},
{6, 7}, {7, 8},
{8, 9}, {2, 9}.

A vertex cover of G is

{1, 3, 5, 7, 9}.

Notice that each edge of G contains at least one of the vertices in that set.


The Vertex Cover problem is the following decision problem.

Input. An undirected graph G and a positive integer k.

Question. Does G have a vertex cover of size no more than k?

Suppose that G is the graph above and k is 4. Does G have a vertex cover of size no more than 4? Yes! {2, 4, 6, 8}.


Nobody knows a polynomial-time (deterministic) algorithm that solves the Vertex Cover problem.

But there is a nondeterministic polynomial-time algorithm for the Vertex Cover problem, as follows.

The evidence is a set of vertices.

Evidence e is accepted as evidence that G has a vertex cover of size no more than k if

  1. e is a set of vertices of G,

  2. the size of e is no more than k,

  3. every edge of G contains at least one member of e.

So the Vertex Cover problem is in NP.


A rule of thumb for finding nondeterministic algorithms

Problems that have nondeterministic algorithms are typically expressed as a question: "Does there exist … so that …"

For example, COMPOSITE asks, for a given positive integer k, whether there exists an ordered pair (i, j) so that 1 < i, j < k and k = ij.

The Vertex Cover problem asks, for a given pair (G, k), whether there exists a set S of vertices of G so that S has no more than k members and every edge of G contains at least one member of S.

A nondeterministic algorithm to answer question

"Does there exist A so that B?"

Look at the nondeterministic algorithms above to see that they fit into that scheme.