P (complexity)

In the study of computational complexity, P is a fundamental class of problems. It is also known as PTIME or DTIME(nO(1)). This class includes decision problems that a deterministic Turing machine can solve in polynomial time. A decision problem is a question that requires a simple "yes" or "no" answer. In computer science, P represents tasks that are considered "efficiently solvable" or "tractable."

This idea is known as Cobham's thesis. While the term "efficient" is not always perfectly accurate in practice, it serves as a very useful rule of thumb for researchers.

To understand the mechanism of P, we must look at how a deterministic Turing machine operates. For any language or problem in P, there must exist a specific machine, often called M. This machine processes an input, which we call x. If the input x belongs to the language, the machine must output a 1. If the input x does not belong to the language, the machine must output a 0. The most important rule is that the machine must finish its work in polynomial time for all possible inputs.

This means the time required grows at a rate related to a power of the input size.

Beyond Turing machines, P can also be described using Boolean circuits. A language is in P if there is a uniform family of these circuits. Each circuit takes a specific number of bits as input and produces a single bit as an output. For an input x, the circuit outputs 1 if x is in the language and 0 if it is not. This circuit definition can even be weakened to use a logspace uniform family without changing the actual complexity class.

Many important mathematical problems belong to the class P. For example, the decision versions of linear programming are in P. Finding a maximum matching is another example. A major breakthrough occurred in 2002 when scientists proved that determining if a number is prime is in P. There are also problems known as P-complete problems, which are the most difficult within the class. One such example is st-connectivity, also called reachability, on alternating graphs.

The history of these ideas spans over a century. In 1910, H. C. Pocklington analyzed algorithms for solving quadratic congruences. He noticed that some algorithms took time proportional to a power of the logarithm of the modulus. He contrasted this with algorithms that were much slower. This was an early way of distinguishing polynomial time from exponential time. Later, in 1965, Alan Cobham and Jack Edmonds are generally credited with inventing the formal notion of polynomial time. A researcher named Michael Rabin also developed the concept independently around the same time.

Complexity theory uses P to map out relationships between different classes of problems. P is a subset of NP, which is the class of problems solvable by a non-deterministic Turing machine in polynomial time. Most experts believe P is a proper subset of NP, but this remains an unproven hypothesis. P is also larger than the class L, which uses a logarithmic amount of memory space. However, P is no larger than PSPACE, the class of problems solvable using polynomial space.

One thing we do know for certain is that P is strictly contained within EXPTIME, the class of problems solvable in exponential time.

Finally, P has unique mathematical properties that make it robust. Polynomial-time algorithms are closed under composition. This means if one polynomial-time function calls another, the entire process remains in P. This property helps make P a machine-independent class. It also means that P is closed under many operations, such as reversal, intersection, union, and complementation. Even when we do not have a concrete algorithm, such as in the case of the Robertson–Seymour theorem, we can sometimes prove that a polynomial-time algorithm must exist.