The complexity class NP

NP is often described informally as the class of all problems for which there exists a polynomial-time verification that the answer is yes, if it is yes. For instance, the problem "Is the graph G tripartite?" is in NP, because if it is tripartite, and someone shows you a proper 3-colouring, it takes only polynomial time to check that what they have shown you really is a proper 3-colouring. Similarly, the problem of whether a number n is composite is clearly in NP (though in fact it is now known to be in P) since if someone tells you that n=ab, then you can check in polynomial time whether they are telling the truth, by simply multiplying a and b together (which takes time roughly comparable to the product of the numbers of digits of a and b if you don't try to use any clever methods).

More formally, let [math]\displaystyle{ I=\bigcup_{n=1}^\infty\{0,1\}^n }[/math] and let [math]\displaystyle{ f:I\rightarrow\{0,1\} }[/math] be a Boolean function. We say that f belongs to NP if there is a polynomial p and a function [math]\displaystyle{ g:\bigcup_{n=1}^\infty\{0,1\}^{n+p(n)}\rightarrow\{0,1\} }[/math] such that g belongs to P, and such that f(x)=1 if and only if there exists y such that g(x,y)=1.

Just to unpack what that means, let's return to the example of whether or not a graph is tripartite. Here, we encode a graph G in some obvious way as a binary sequence. Then we encode 3-colourings C of the vertices of G in some obvious way as well. Then let g(G,C)=1 if and only if C is a proper 3-colouring of G. Obviously, g can be calculated in polynomial time, and a graph G is tripartite if and only if there exists C such that g(G,C)=1.

Similarly, because the function g(n,a,b), which outputs 1 if a and b are greater than 1 and ab=n, and 0 otherwise, is computable in polynomial time, and since n is composite if and only if there exists a pair (a,b) with g(n,a,b)=1, we find that the problem "Is n composite?" belongs to NP.