Polynomial time

Polynomial time is a running-time bound in which an algorithm's steps grow no faster than a polynomial function of input size. It is the standard notion of efficient computation in complexity theory.

Input size: A measure of the length or scale of an instance supplied to an algorithm. Polynomial-time bounds measure growth against this quantity.
P (complexity): The class of decision problems solvable by a deterministic algorithm in polynomial time. It collects the decision problems polynomial time can solve.
Exponential time: A running-time bound that grows exponentially with input size. Its asymptotic growth is far faster than any fixed polynomial.
NP-completeness: The study of decision problems in NP to which every problem in NP reduces in polynomial time. A polynomial-time algorithm for any NP-complete problem would give polynomial-time algorithms for all problems in NP.
P versus NP problem: The open question of whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. It asks whether polynomial time captures all efficiently verifiable problems.
Big O notation: A notation that describes an asymptotic upper bound on a function's growth. It expresses polynomial running-time upper bounds while ignoring constant factors and lower-order terms.
Deterministic algorithm: An algorithm whose next step is uniquely determined by its current state and input. Polynomial time usually bounds the steps of deterministic algorithms when defining P.
Logarithmic time: A running-time bound proportional to the logarithm of input size. It is a much tighter bound, typical of algorithms that inspect only a small part of the input.
Integer factorization: The problem of expressing a composite integer as a product of prime factors. No classical polynomial-time algorithm is known, making its status relevant to cryptographic security.
BQP: The class of decision problems solvable by a quantum computer in polynomial time with bounded error. It tests whether quantum computation can solve problems beyond classical polynomial time.

Linked from 9 pages