Opening Exponential Time Hypotheses: ETH and SETH
Exponential Time Hypotheses: ETH and SETH
- Length
- 24 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Worst case algorithms for k-SAT
The Exponential Time Hypothesis (ETH) and its strong form (SETH) ask how much exponential time -SAT requires, a question finer than whether P equals NP. O'Donnell starts from brute force and Schöning's Walk-SAT algorithm, which flips variables in unsatisfied clauses and solves 3-SAT in about time. ETH, due to Impagliazzo and Paturi, claims 3-SAT needs time for some . A reduction then shows planar Hamiltonian path needs exponential time too. SETH says -SAT time approaches as grows. The Backurs–Indyk reduction turns SETH into a lower bound for edit distance in this graduate session of CMU 15-750, A Theorist's Toolkit.
Your comment is kept while you sign up.Sign in
Runs from Schöning's random-walk 3-SAT algorithm to a SETH-conditional lower bound for edit distance.
The Exponential Time Hypothesis (ETH) and its strong form (SETH) ask how much exponential time -SAT requires, a question finer than whether P equals NP. O'Donnell starts from brute force and Schöning's Walk-SAT algorithm, which flips variables in unsatisfied clauses and solves 3-SAT in about time. ETH, due to Impagliazzo and Paturi, claims 3-SAT needs time for some . A reduction then shows planar Hamiltonian path needs exponential time too. SETH says -SAT time approaches as grows. The Backurs–Indyk reduction turns SETH into a lower bound for edit distance in this graduate session of CMU 15-750, A Theorist's Toolkit.
A new method for local search—on satisfiability
Complexity of the k-SAT problem
Backurs and Indyk (2015)
Backurs-Indyk '13
This lecture
Lecture 84 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.