ConceptTheory & Algos
Computational complexity
The study of the resources, such as time and space, required to solve computational problems.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Algorithm2Algorithmic complexity1Basic computation1Big O notation1Computer program1Convolutional neural networks1Gravity1Input size1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
4Each in their own terms, from the easiest level.
Fei-Fei Li, Justin Johnson & Serena Yeung
The amount of computational resources, such as operations, required to perform a calculation.Erik Demaine
Computational complexity classifies problems according to their inherent difficulty and the amount of resources like time required to solve them.Leonard Susskind
A concept from computer science relating to the resources needed to solve computational problems, now being connected to quantum mechanics and geometry.
Lectures that assume it
32The first 12 are shown.
- Randomized Complexity: RP, coRP, and ZPP
- Geometric Problems Continued
- Why AI is Harder Than We Think
- Hardness within P
- Bentley Rules for Optimizing Work
- Stream Ciphers, Random Numbers and the One Time Pad
- Complexity: P, NP, NP-completeness, Reductions
- Cryptography: Encryption
- Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- Green HPC: Paving the Way for Sustainable Supercomputing
- Simon's Algorithm
- Architectures: Memory
Connections
45The lectures that define it or assume it, and the concepts next to it.
Concepts9
Show 3 moreShow fewer
Lectures36
- CNN Architectures
- Computational Complexity
- ER = EPR: Wormholes, Horizon Firewalls, and Entanglement
- 10^500 Parallel Universes
- Randomized Complexity: RP, coRP, and ZPP
- Geometric Problems Continued
Show 30 moreShow fewer
- Why AI is Harder Than We Think
- Hardness within P
- Bentley Rules for Optimizing Work
- Stream Ciphers, Random Numbers and the One Time Pad
- Complexity: P, NP, NP-completeness, Reductions
- Cryptography: Encryption
- Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- Green HPC: Paving the Way for Sustainable Supercomputing
- Simon's Algorithm
- Architectures: Memory
- How Hard is too Hard? An Introduction to Complexity
- NP-Completeness Reductions
- Computing, Life, and Intelligence
- Bellman-Ford
- AI in Science and Engineering: Towards Trustworthy AI and Quantum Technologies
- NP-Completeness and the Cook-Levin Theorem
- The Mystery of 3-Manifolds
- Why is P vs. NP Difficult?
- Nobel Lecture: Auction Theory and Practical Market Design
- Proofs, Knowledge, and Computation: Zero-Knowledge Interactive Systems
- Multi-Way Join Algorithms / Worst-Case Optimal Joins
- Provably Intractable Problems, Oracles
- Quantum Computing for Computer Scientists
- Applications of Jordan Canonical Form in LDS and Electrical Engineering
- Time Complexity
- Work Trades Off with Complexity in Computationally Restricted Thermodynamics
- Quantum Algorithms Synthesis II: Grover's Search & Circuit SAT
- Epilogue: The Map of Machine Learning
- Quantum Computing Overview
- Cryptographic Proofs, Lattices & Hardness Assumptions: A Polylogue