Computational Complexity in Theory and in Practice by Richard M. Karp

Explore the contrasting approaches to algorithm efficiency in theoretical computer science and practical computing in this 1-hour 17-minute distinguished lecture by Professor Emeritus Richard M. Karp. Delve into theoretical concepts such as complexity classes P and NP, NP-completeness, approximation algorithms, and hardness of approximation. Examine practical applications including satisfiability solvers, linear and integer programming, the traveling salesman problem, deep learning algorithms, and game-playing programs based on reinforcement learning. Gain insights into the metrics used for evaluating algorithms in both theoretical and practical contexts, comparing worst-case performance analysis with empirical performance evaluation.