Editing P (complexity) (section)

{{short description|Class of problems solvable in polynomial time}}
In [[computational complexity theory]], '''P''', also known as '''PTIME''' or '''[[DTIME]]'''(''n''<sup>O(1)</sup>), is a fundamental [[complexity class]]. It contains all [[decision problem]]s that can be solved by a [[deterministic Turing machine]] using a [[polynomial]] amount of [[computation time]], or [[polynomial time]].

[[Cobham's thesis]] holds that P is the class of computational problems that are "efficiently solvable" or "[[tractable problem|tractable]]". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful [[rule of thumb]].