Sign inSign in

Time hierarchy theorem

A theorem stating that giving a Turing machine more time allows it to solve strictly more problems.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 10 definitions
Watch it explained

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

3

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    A foundational theorem in computational complexity stating that more time allows Turing machines to compute strictly more languages.
    • 6:51Hardness within P
    • 1:10:13The Complexity Class NP
    • 1:01:08Time Complexity and Universal Turing Machines
    • 0:06Hierarchy Theorems (Time, Space, and Nondeterministic)
    • 0:03Time Hierarchy Theorem
    • 13:51Course Introduction and Overview
    • 4:57Why is P vs. NP Difficult?
  • Michael Sipser

    MIT · Undergraduate

    A theorem stating that if a Turing machine is given more time, it can solve more problems.
  • Seth Pettie

    University of Michigan · Research

    A theorem stating that having more time on a Turing machine allows problems to be solved that cannot be solved in less time.
    • 0:45Strange Gaps in the Local Time Hierarchy

Lectures that assume it

3

Connections

21

The lectures that define it or assume it, and the concepts next to it.

Concepts8

Show 2 more

Lectures13

Show 7 more

3 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.