In computational complexity theory [Computational complexity theory], P, also known as PTIME or DTIME(\(n^{\bigo{1}}\)), is a fundamental complexity class. It contains all decision problems 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”. 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.
Bibliography
“P (Complexity).” 2022. Wikipedia, October. https://en.wikipedia.org/w/index.php?title=P_(complexity)&oldid=1113888801.