The complexity class P

In computer-science speak, a problem is not a single question with a yes/no answer, but rather a question that applies to all members of some class of possible inputs. For example, "Is n prime?" is a problem in this sense: the input is the number n, and the answer is yes if n is prime and no if it is composite. A question such as "Is 1037 prime?" would be described as a problem instance.

Problems can easily be encoded as Boolean functions. For example, we can encode numbers like 1037 as strings of 0s and 1s by writing them in binary, and given a binary string x, we can define f(x) to be 1 if the answer to the particular problem is yes for x, and 0 otherwise. Formally, we are regarding a problem as a function from [math]\displaystyle{ \bigcup_{n=1}^\infty\{0,1\}^n }[/math] to [math]\displaystyle{ \{0,1\} }[/math].

A problem belongs to the complexity class P if there is an algorithm that solves it in a time that is bounded above by a polynomial of the input size. For instance, a famous recent theorem asserts that primality testing belongs to P. This means that there is an algorithm that will tell you in polynomial time whether a given integer is prime or composite. Note that "in polynomial time" means that it will tell you whether n is prime in a time that is polynomial in the number of digits of n, rather than in n itself, or in other words, it runs in a time that is something like [math]\displaystyle{ (\log n)^C }[/math]. This is because it is the number of digits of n that is the appropriate measure of the size of the input for the problem: it isn't exactly a challenge to come up with a primality testing algorithm that takes a time that is polynomial in n.

Another problem that gives a good illustration of the complexity class P is this. You input a graph G and answer the question "Is G bipartite?" To input the graph, you label the m vertices and then specify for each pair (i,j) of vertices whether ij is an edge. The size of this input is [math]\displaystyle{ n=\binom m2 }[/math]. To show that G is bipartite, you have to find a partition of the vertices into two classes inside which there are no edges. To do this by brute force one would have to check all [math]\displaystyle{ 2^{n-1} }[/math] bipartitions of the vertices, which would be an exponential-time algorithm. Fortunately, there is a much better way: we build up a colouring of the vertices as follows. Start at an arbitrary vertex and colour it red. Then colour all its neighbours blue. Then colour all their (not yet coloured) neighbours red again. Keep going until you either reach a vertex that you want to colour both red and blue (in which case the graph is not bipartite) or you have no neighbours to colour. If there are still uncoloured vertices (which is possible if the graph is not connected) then find a new vertex and repeat the procedure. It is easy to see that this algorithm can be implemented in polynomial time.

By contrast, if you try to find a polynomial-time algorithm for testing whether a graph is tripartite (or 3-colourable), then you will almost certainly fail: it is believed that no such algorithm exists. See the discussion of NP for more on this problem.