P (complexity)

Computers solve many puzzles. Some puzzles are fast to solve.

We call these fast puzzles P. They are easy for a machine. They do not take too long.

Finding if a number is prime is in P. This means a computer can do it fast.

Some hard puzzles are not in P. But many useful tasks are.

We use P to help us build good machines. It is a very helpful rule.

Computers solve many types of puzzles. Some puzzles are easy to solve. We call these "efficient" problems. This means a computer can solve them in a reasonable amount of time.

In math, we call this group of problems P. A problem is in P if it can be solved in "polynomial time." This is a way to measure how long a task takes. As the task gets bigger, the time it takes does not grow too fast.

Many real tasks are in P. For example, finding if a number is prime is in P. This was shown in 2002. Other tasks like finding a "maximum matching" are also in P.

Scientists use P to group different kinds of problems. P is a part of a larger group called NP. We do not know if P and NP are the same. Most experts think they are different. We also know that P is smaller than a group called EXPTIME. Problems in EXPTIME take much longer to solve. P helps us understand what computers can do well.

Computers solve many different kinds of puzzles every day. Some of these puzzles are easy for a computer to finish quickly. We call these "efficiently solvable" problems. In math, this group of problems is called P.

This name comes from the idea of polynomial time. When a task gets bigger, the time it takes to finish does not explode. It grows at a steady, manageable rate. This makes P a very important class in computer science.

To understand how P works, think about how a machine follows steps. A machine called a deterministic Turing machine can solve these problems. It follows a clear path to find an answer. For every problem in P, the machine must give a simple answer. It says "1" if the answer is yes. It says "0" if the answer is no.

The machine must do this using a polynomial amount of time. This means the work stays within a certain limit as the input grows.

People have studied these ideas for a long time. In 1965, researchers named Cobham and Edmonds helped create this idea. They wanted a way to describe efficient algorithms. Another scientist named Rabin also found this idea around that same time. Even earlier, in 1910, H. C. Pocklington looked at how long math tasks took. He noticed some tasks were much faster than others. He saw a difference between fast math and very slow math.

There are many famous problems that belong in the P group. For a long time, we did not know if prime numbers were in P. Then, in 2002, scientists proved that checking if a number is prime is in P.

Other problems like linear programming are also in P. Some problems are even called P-complete. These are the hardest problems within the P group.

They help us understand the limits of what is easy for computers.

Scientists also use P to compare different groups of math problems. P is a part of a much larger group called NP. Most experts believe P is smaller than NP, but they have not proven it yet.

We also know that P is smaller than a group called EXPTIME. Problems in EXPTIME take a huge amount of time to solve. P is also larger than a group called L, which uses very little memory.

Comparing these groups helps us map out the world of math.

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.