Sign inSign in

Exponential time hypothesis

The assumption that 3SAT cannot be solved in sub-exponential time 2δn2^{\delta n} for some δ>0\delta > 0.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 9 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.

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

    • 4:27Exponential Time Hypotheses: ETH and SETH
    • 5:01The Complexity Class NP
    • 0:06The Exponential Time Hypothesis: Foundations of Computational Hardness
    • 13:36Beyond Worst-Case Analysis
    • 12:50Quantum Algorithms Synthesis II: Grover's Search & Circuit SAT
    • 22:47Quasilinear Cook–Levin Theorem
  • Venkatesan Guruswami

    Carnegie Mellon University · Undergraduate

    The conjecture that 3SAT cannot be solved in sub-exponential time such as 2ϵ0n2^{\epsilon_0 n}.
    • 1:01:54BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
  • Barna Saha

    UC Berkeley · Graduate

    The assumption that 3-SAT cannot be solved in sub-exponential time $2^{o(n)}.
    • 0:53Efficient Fine-Grained Algorithms

Lectures that assume it

1

Connections

16

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

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.