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
V(x, e) runs in polynomial time in the lengths of its inputs, x and e.
(V is reasonable.)
There is an integer k so that,
for every integer n
and every string x of length n
if x ∈ L then
there exists a string e whose
length is ≤ nk so that
V(x, e) returns true.
(V is not gullible.)
If x ∉ L then
for every e (no matter how long),
V(x, e) = false.
An integer k is composite if k > 1 and there are two integers i and j, where 1 < i, j < k, so that k = i⋅j.
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
Notice that
Correct evidence is only about twice the length of k, so it is short.
If k is composite then there exists correct evidence (i, j) so that Check(k, (i, j)) accepts.
If k is not composite then Check(k, e) rejects for every possible evidence e. ◊
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
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
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
e is a set of vertices of G,
the size of e is no more than k,
every edge of G contains at least one member of e.
So the Vertex Cover problem is in NP.
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 = i⋅j.
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
uses, as evidence, the thing A that is supposed to exist.
It checks the evidence by making sure that B is true of that evidence.
Look at the nondeterministic algorithms above to see that they fit into that scheme.