# Difference between revisions of "The complexity class P"

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 $\bigcup_{n=1}^\infty\{0,1\}^n$ to $\{0,1\}$.
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 $(\log n)^C$. 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 $n=\binom m2$. 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 $2^{n-1}$ 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.