Polynomial time

An algorithm runs in polynomial time when its running time is at most $O(n^k)$ for some constant $k$, where $n$ is the input length.

An algorithm runs in polynomial time if its worst-case running time is bounded by a fixed polynomial in the input length. Arithmetic with fixed-degree algebraic numbers also needs polynomial bit cost when used in such a guarantee. The Edmonds–Karp algorithm and the method of conditional probabilities with efficiently computable clause expectations are examples.

$\mathbf{P}$ is the class of decision problems decidable by a deterministic computation in polynomial time.

A language in P to which every P language has a logspace many-one reduction. The reduction strength matters: using arbitrary polynomial-time reductions instead would make completeness trivial for nontrivial P decision problems.

$\mathbf{NP}$ is the class of decision problems whose positive instances have polynomial-length certificates verifiable in polynomial time. Equivalently, it is polynomial time on a nondeterministic computation.

A certificate for a positive instance is a polynomial-length string that makes a polynomial-time verifier accept that instance.