Complexity Classes¶

Problems cluster into fundamental classes (constant, logarithmic, linear, polynomial, exponential) based on inherent computational requirements, defining boundaries of practical tractability.

Tension Addressed¶

Exact vs. Approximate Solutions (exponential classes force approximation)

Recognizable As¶

O(1) hash lookups; O(log n) binary search patterns; O(n log n) sorting bounds; exponential blowup in combinatorial features; "polynomial time" as tractability benchmark

Canonical Sources¶

Hartmanis and Stearns, On the Computational Complexity of Algorithms (1965); Cook, The Complexity of Theorem Proving Procedures (1971)

Transfers To¶

Cryptography (hardness assumptions), scheduling systems, compiler optimization, constraint solvers, resource allocation

The hierarchy of complexity classes represents mathematical truths about computation itself, not artifacts of current technology.