P (complexity)

Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable".

A language L is in P if and only if there exists a deterministic Turing machine M, such that P can also be viewed as a uniform family of Boolean circuits.

, such that The circuit definition can be weakened to use only a logspace uniform family without changing the complexity class.

P is known to contain many natural problems, including the decision versions of linear programming, and finding a maximum matching.

space cannot use more than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.")

If a problem is in P/poly, then it can be solved in deterministic polynomial time provided that an advice string is given that depends only on the length of the input.

Unlike for NP, however, the polynomial-time machine doesn't need to detect fraudulent advice strings; it is not a verifier.

This is also one of the main reasons that P is considered to be a machine-independent class; any machine "feature", such as random access, that can be simulated in polynomial time can simply be composed with the main polynomial-time algorithm to reduce it to a polynomial-time algorithm on a more basic machine.

Languages in P are also closed under reversal, intersection, union, concatenation, Kleene closure, inverse homomorphism, and complementation.

In descriptive complexity, P can be described as the problems expressible in FO(LFP), the first-order logic with a least fixed point operator added to it, on ordered structures.

Kozen[12] states that Cobham and Edmonds are "generally credited with the invention of the notion of polynomial time," though Rabin also invented the notion independently and around the same time (Rabin's paper[13] was in a 1967 proceedings of a 1966 conference, while Cobham's[14] was in a 1965 proceedings of a 1964 conference and Edmonds's[15] was published in a journal in 1965, though Rabin makes no mention of either and was apparently unaware of them).