= Computational complexity theory
{wiki}
<Computational complexity theory> studies the resources required to solve families of <computational problems>. A statement specifies an <input> encoding and a <model of computation>, then measures resources such as <running time>, <computer memory> or <query complexity> as the encoded <input> length grows. An <algorithm>'s upper bound describes one method; a problem lower bound constrains every permitted <algorithm> in the stated model.
For <decision problems>, a <complexity class> collects problems with a shared resource guarantee. <P> uses deterministic <polynomial time>; <NP> permits polynomially bounded witnesses checked in <polynomial time>. The distinction separates finding an answer from verifying a supplied certificate.<The P versus NP Problem by Stephen A. Cook>[§1, definitions of P and NP]{ref}
The cost model is part of the mathematics. <Bit complexity> charges for arithmetic on operands of growing size, while a <comparison model> counts comparisons of keys. A <polynomial-time algorithm> also need not be practical at every scale: its exponent and constants still affect actual <running time>. These distinctions make complexity bounds useful for comparing both mathematical possibilities and concrete implementations.
Back to article page
