Computational complexity theory

Computational complexity theory studies the resources needed to solve computational problems and classifies problems by how those requirements grow with input size.

Computational problem: A computational problem specifies inputs and the required outputs or decisions for those inputs. Complexity analysis measures the resources needed to solve problems across their possible inputs.
Time complexity: Time complexity measures how an algorithm's number of computational steps grows with input size. It captures the time resource studied in the theory's central classifications.
P (complexity): P is the class of decision problems solvable by a deterministic algorithm in polynomial time. It formalizes the class commonly treated as efficiently solvable.
Alan Turing: Alan Turing was a British mathematician whose work founded key ideas in computation and mathematical logic. His abstract machine became a foundation for defining computation and its resources.
Travelling salesman problem: The travelling salesman problem asks for a shortest tour visiting each city once and returning to the start. Its optimization form exemplifies problems that are hard to solve exactly at scale.
Algorithm: An algorithm is a finite, precise procedure for producing an output or solving a problem. Resource bounds describe how much time and memory an algorithm uses.
Space complexity: Space complexity measures how an algorithm's memory use grows with input size. It classifies problems by memory requirements rather than running time.
NP (complexity): NP is the class of decision problems whose yes-instances have certificates verifiable in polynomial time. Its relationship to P captures the distinction between finding solutions and checking them.
Stephen Cook: Stephen Cook is a computer scientist known for proving the NP-completeness of Boolean satisfiability. His 1971 result established a central method for demonstrating computational hardness.
Approximation algorithm: An approximation algorithm efficiently finds a solution guaranteed to be within a specified bound of optimal. Approximation provides useful answers when exact optimization is computationally intractable.

Linked from 42 pages