The complexity class of decision problems that can be solved by a deterministic algorithm in a running time that grows polynomially with the size of the input; widely, though not provenly, treated as the class of problems that are efficiently solvable in practice.
Facts
Core PrincipleThe class of decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time. 1 Connections
Sources
1. P (complexity), Wikipedia
Lead section, second sentence
It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
In Group: Polynomial and Nondeterministic Time Classes, Lead
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.