Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore the fundamental SAT (Boolean Satisfiability) problem and its connection to the famous P vs NP question in this Members' Colloquium lecture. Discover how the search for algorithms that can beat exhaustive search over all 2^n possibilities has led to unexpected connections and new research areas in computer science. Learn about the "algorithmic method," which derives computational hardness results from SAT algorithms that outperform brute-force approaches, and how this technique has produced long-sought hardness results for specific algorithm types. Examine the surprising relationship between improving efficient algorithms for "easy" problems like computing shortest paths in graphs and developing better SAT algorithms. Understand how these discoveries contribute to the emerging field of "fine-grained complexity," which investigates the optimality of textbook algorithms and the consequences of improving them. The lecture traces the speaker's persistent efforts to find faster SAT algorithms and the intellectual surprises encountered along the way, including how failures in one direction opened up entirely new research directions. No special background knowledge is required to follow this exploration of one of computer science's most important open problems and its unexpected ramifications across multiple areas of theoretical computer science.
