ConceptTheory & Algos
Polynomial time
An algorithm whose running time is bounded by a polynomial function of the input size.
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.
Big O notation1Input size1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
1Lectures that assume it
63The first 12 are shown.
- Course Overview, Interval Scheduling
- The Complexity Class coNP
- Complexity: Fixed-Parameter Algorithms
- Computational Indistinguishability
- Exponential Time Hypotheses: ETH and SETH
- Randomized Complexity: RP, coRP, and ZPP
- Hardness within P
- Complexity: P, NP, NP-completeness, Reductions
- The Immerman-Szelepcsényi Theorem
- Complexity: Approximation Algorithms
- Pseudorandom Generators
- Constraint Satisfaction Problems
Connections
70The lectures that define it or assume it, and the concepts next to it.
Lectures64
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Course Overview, Interval Scheduling
- The Complexity Class coNP
- Complexity: Fixed-Parameter Algorithms
- Computational Indistinguishability
- Exponential Time Hypotheses: ETH and SETH
Show 58 moreShow fewer
- Randomized Complexity: RP, coRP, and ZPP
- Hardness within P
- Complexity: P, NP, NP-completeness, Reductions
- The Immerman-Szelepcsényi Theorem
- Complexity: Approximation Algorithms
- Pseudorandom Generators
- Constraint Satisfaction Problems
- Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- P and NP, SAT, Poly-Time Reducibility
- How Hard is too Hard? An Introduction to Complexity
- Complexity and Computability with Closed Timelike Curves
- The Complexity Class NP
- Reductions
- Time/Space Tradeoffs for SAT
- CSP Approximability: Optimization and Certification
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Interactive Proofs: IP=PSPACE
- Ironic Complexity
- Time Complexity and Universal Turing Machines
- Search-to-Decision, Padding, Dichotomy Theorems
- Toda's 1st Theorem and the Permanent
- NP-Completeness
- Cook-Levin Theorem
- Efficient Fine-Grained Algorithms
- Course Introduction and Overview
- Boolean Satisfiability (SAT)
- Circuits
- Probabilistic Complexity Classes
- NP-Completeness and the Cook-Levin Theorem
- Ladner's Theorem and Mahaney's Theorem
- From P-Completeness to PSPACE-Completeness
- Computational Complexity
- Probabilistic Computation
- Interactive Proof Systems, IP
- Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- Linear Programming: Optimization Reduces to Feasibility
- The Ellipsoid Algorithm
- Oracle Turing Machines and P^NP
- Mathematics and Computation: The Landscape of P vs. NP
- Proofs, Knowledge, and Computation: Zero-Knowledge Interactive Systems
- Space Complexity, PSPACE, Savitch's Theorem
- Provably Intractable Problems, Oracles
- Problems in P
- Nondeterminism
- Valiant–Vazirani Theorem, and Exact Counting (#P)
- Expander Graphs Overview
- Quantum Complexity
- Time Complexity
- Probabilistic Computation, BPP
- Rotate, Compute, Rotate
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Introduction to Arthur-Merlin classes, MA and AM
- Beyond Worst-Case Analysis
- Quantum Algorithms Synthesis II: Grover's Search & Circuit SAT
- The Polynomial Time Hierarchy
- Computational Thinking on Learning Models
- Quasilinear Cook–Levin Theorem
- Quantum Algorithms Synthesis III: Efficient Factoring & BQP