Opening Hardness within P
Hardness within P
- Length
- 1 h 22 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 7: Hardness within P
Reduces CNF-SAT to graph diameter, showing that a faster-than- diameter algorithm would break SETH.
Fine-grained complexity seeks the exact polynomial running times of natural problems, because polynomial time alone says little about massive inputs. O'Donnell starts from longest common subsequence and matrix multiplication, then states the Strong Exponential Time Hypothesis: CNF-SAT needs close to time. Session 27 of CMU 15-455 also surveys 3SUM, APSP and -clique, and explains why fine-grained reductions must track instance-size blow-up alongside running time. The main proof builds a graph whose vertices stand for clauses and partial assignments. Under SETH, graph diameter then cannot be computed much faster than , even approximately. The material assumes polynomial-time reductions, breadth-first search and CNF-SAT.
Fine-grained complexity seeks the exact polynomial running times of natural problems, because polynomial time alone says little about massive inputs. O'Donnell starts from longest common subsequence and matrix multiplication, then states the Strong Exponential Time Hypothesis: CNF-SAT needs close to time. Session 27 of CMU 15-455 also surveys 3SUM, APSP and -clique, and explains why fine-grained reductions must track instance-size blow-up alongside running time. The main proof builds a graph whose vertices stand for clauses and partial assignments. Under SETH, graph diameter then cannot be computed much faster than , even approximately. The material assumes polynomial-time reductions, breadth-first search and CNF-SAT.
Paper by de Berg, van Kreveld, and Overmars
Impaliazo, Paturi, and Zane (2001)
ACM '96 paper
This lecture
Lecture 27 of 28 of Undergraduate Complexity Theory.
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.
Your comment is kept while you sign up.Sign in