definition

Complexity Means Scaling of Resources

In theoretical computer science, computational complexity refers to the resources (most fundamentally time and memory/space) needed to solve a problem, and crucially what matters is how those resources scale with problem size, not absolute figures that depend on the particular machine used.

definitionpending

Speaker

Scott Aaronson

Evidence Quote

“what people mean by complexity, let's say, by computational complexity is the resources that are needed to solve some problem, and specifically, what we care about is the scaling of the resources”

Source

99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity— Sean Carroll's Mindscape
Created: 6/13/2026, 12:26:25 AM

Your notes

Loading notes...