ConceptTheory & Algos
Time hierarchy theorem
A theorem stating that giving a Turing machine more time allows it to solve strictly more 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.
Time complexity9Turing machine9Deterministic Turing machines3Big O notation2Complexity class2Complexity classes2Time constructible function2Complexity classes P and EXP1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
A foundational theorem in computational complexity stating that more time allows Turing machines to compute strictly more languages.Michael Sipser
A theorem stating that if a Turing machine is given more time, it can solve more problems.Seth Pettie
A theorem stating that having more time on a Turing machine allows problems to be solved that cannot be solved in less time.
Lectures that assume it
3Connections
21The lectures that define it or assume it, and the concepts next to it.
Concepts8
- Time complexity
- Turing machine
- Big O notation
- Delayed diagonalization
- Indirect diagonalization
- Kannan's theorem