A known algorithm (or turing machine) that is guaranteed to terminate within a number of steps which is a polynomial function of the size of the problem.

See also computational complexity, exponential time, nondeterministic polynomial-time (NP), np-complete.