computational complexity
The minimal number of simple steps required to go from a starting point to a result, used as a measure of how hard a computation or proof is.
As defined in 45 | Leonard Susskind on Quantum Information, Quantum Gravity, and Holography
Where it comes up · 5
- Gary Marcus on the Future of Artificial Intelligence and the Brain2 claims
- 45 | Leonard Susskind on Quantum Information, Quantum Gravity, and Holography2 claims
- 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity2 claims
- 272 | Leslie Valiant on Learning and Educability in Computers and People1 claim
- AMA | August 20211 claim
Most important claims · 8 of 8Search all claims for “computational complexity” →
- The computational complexity of a thing or process is the absolute minimal number of simple steps required to go from a starting point to it—not the number some person happened to use; a theorem's difficulty is its minimal number of logical operations from the postulates, so a simply stated theorem like the four-color theorem can be highly complex while Pythagoras is simple.45 | Leonard Susskind on Quantum Information, Quantum Gravity, and Holography
- A black hole evolving in time is carrying out a quantum computation, and the computational complexity of that evolution has a direct meaning as the growing volume of the interior of the black hole—linking the geometric growth of a black hole's interior to the increasing complexity of its quantum state.45 | Leonard Susskind on Quantum Information, Quantum Gravity, and Holography
- A complete brain simulation may need to go down to the level of individual molecules, making computational complexity so vast that running it in real time is basically impossible for the foreseeable future; like weather forecasting, small errors compound chaotically (butterfly effect) so detailed behavioral prediction beyond a few seconds becomes intractable.Gary Marcus on the Future of Artificial Intelligence and the Brain
- Among the topics studied in AI, learning is the most fundamental, because a theory of computation is worthless if it cannot address the basic problems of the mind, and learning turned out to be the entry point that was computationally feasible whereas logical reasoning proved computationally intractable.272 | Leslie Valiant on Learning and Educability in Computers and People
- Intelligent simulation that incorporates understanding of underlying principles is far more efficient than blind brute-force simulation at the level of individual molecules, which runs back into intractable computational complexity.Gary Marcus on the Future of Artificial Intelligence and the Brain
- Harlow and Hayden's subtle point is not that contradictions are acceptable if hard to discover, but that the contradictions in effective field theories (which must ultimately be superseded by quantum gravity) may surface not at extreme energies or tiny distances but in regimes of extreme computational complexity; if exposing such a breakdown requires an exponential computation, then we have a principled reason to trust effective field theory in normal situations.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- 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.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- The halting problem and the traveling salesman problem are not really related: the traveling salesman problem is hard (takes many steps) but solvable, whereas the halting problem is literally unsolvable — there is no way to determine just by inspecting a program whether it will halt, since running it can only ever confirm halting within a finite time, never prove it never halts.AMA | August 2021