Klassen av språk som lar seg gjenkjenne av klassiske polynomtidalgoritmer. Fra [Complexity Zoo](https://complexityzoo.net/Complexity_Zoo:P): > ##### P: Polynomial-Time > > The class that started it all. > > The class of decision problems solvable in polynomial time by a Turing machine. (See also [FP](https://complexityzoo.net/Complexity_Zoo:F#fp), for function problems.) > > Defined in [Edm65](https://complexityzoo.net/Zooref#edm65), [Cob64](https://complexityzoo.net/Zooref#cob64), [Rab60](https://complexityzoo.net/Zooref#rab60), and other seminal early papers. > > Contains some highly nontrivial problems, including linear programming ([Kha79](https://complexityzoo.net/Zooref#kha79)) and finding a maximum matching in a general graph ([Edm65](https://complexityzoo.net/Zooref#edm65)). > > Contains the problem of testing whether an integer is prime ([AKS02](https://complexityzoo.net/Zooref#aks02)), an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis ([Mil76](https://complexityzoo.net/Zooref#mil76)). > > A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in [L](https://complexityzoo.net/Complexity_Zoo:L#l) (logarithmic space). The canonical P-complete problem is *circuit evaluation*: given a Boolean circuit and an input, decide what the circuit outputs when given the input. > > Important subclasses of P include [L](https://complexityzoo.net/Complexity_Zoo:L#l), [NL](https://complexityzoo.net/Complexity_Zoo:N#nl), [NC](https://complexityzoo.net/Complexity_Zoo:N#nc), and [SC](https://complexityzoo.net/Complexity_Zoo:S#sc). > > P is contained in [NP](https://complexityzoo.net/Complexity_Zoo:N#np), but whether they're equal seemed to be an open problem when I last checked. > > Efforts to generalize P resulted in [BPP](https://complexityzoo.net/Complexity_Zoo:B#bpp) and [[BQP]]. > > The nonuniform version is [P/poly](https://complexityzoo.net/Complexity_Zoo:P#ppoly), the monotone version is [mP](https://complexityzoo.net/Complexity_Zoo:M#mp), and versions over the real and complex number fields are [PR](https://complexityzoo.net/Complexity_Zoo:P#pr2) and [PC](https://complexityzoo.net/Complexity_Zoo:P#pc) respectively. > > In descriptive complexity, P can be defined by three different kind of formulae, [FO(lfp)](https://complexityzoo.net/Complexity_Zoo:P#Complexity_Zoo:F.23folfp) which is also [FO($n^{O(1)}$)](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f914e568b9b709d92d93b18093c8d4dca9678de))](https://complexityzoo.net/Complexity_Zoo:P#Complexity_Zoo:F.23fot)], and also as [SO(Horn)](https://complexityzoo.net/Complexity_Zoo:P#Complexity_Zoo:S.23sohorn) > > P queries are exactly the one that can be written in the [While/cons](https://complexityzoo.net/Complexity_Zoo:P#Complexity_Zoo:S.23while) languages. > > P is the class of decision problems solvable by a (logspace) *uniform* family of polynomial-size Boolean circuits. > > P can be computed by interactive protocols (see [IP](https://complexityzoo.net/Complexity_Zoo:I#ip)) where the verifier runs in log space (see [L](https://complexityzoo.net/Complexity_Zoo:L#l) and [BPL](https://complexityzoo.net/Complexity_Zoo:B#bpl) ([GKR15](https://complexityzoo.net/Zooref#gkr15))).