Sheela
Sheela
Home
Add
Questions
Thinkers
Claims
People
Concepts
Jargon
Sources
Health
Predictions
Collections
Domain Landscape
Contribute
Review
Dedup
Topic requests
Settings
Help

← Jargon

Jargoncomputer science· 2 claims· 2 episodes

computational complexity theory

The CS field classifying computational problems by how the resources (time, memory) needed to solve them scale with input size.

As defined in AMA | April 2025


Where it comes up · 2
  • AMA | April 20251 claim
  • Scott Aaronson - Quantum Computing, Complexity, and Creativity1 claim

Most important claims · 2 of 2Search all claims for “computational complexity theory” →
  • Computer-science 'complexity theory'—which classifies problems by how time and memory resources scale with input size (e.g. P vs NP)—is a distinct, tightly-defined field that merely shares a name with Santa Fe Institute-style 'complexity theory'; the latter, studying complex adaptive systems, lacks a similarly crisp characterization of which problems fall inside it, making it more of a loose interdisciplinary cluster than a precisely bounded area.AMA | April 2025
  • The reason quantum teleportation (1990s) and quantum computing (1980s) came decades after quantum mechanics (1926) is that viewing entanglement as a usable resource only began with John Bell in the 1960s, computational complexity theory only developed in the 1960s-70s, and meanwhile both physics and the nascent field of classical computing had enormous other priorities, plus WWII diverted fundamental scientists.Scott Aaronson - Quantum Computing, Complexity, and Creativity