Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111

Richard Karp often visualizes algorithms as an iterative process where the distance from the desired solution continuously reduces. He focuses on the 'inner loop' of an algorithm and observes metrics monotonically improving until the optimum is reached, such as in the Traveling Salesman Problem where an objective function is minimized. (Timestamp: 609 seconds)

The Assignment Problem involves matching N boys with N girls (or any two sets) based on a cost matrix, aiming to minimize the total cost of the one-to-one matching. The Hungarian Algorithm solves this problem by iteratively subtracting constants from rows or columns of the cost matrix while maintaining non-negative entries, eventually leading to a permutation of zeros that represents the cheapest assignment. (Timestamp: 813 seconds)

During his PhD in 1955, Richard Karp encountered the Harvard Mark IV, a room-sized computer with visible relays prone to literal 'bugs'. The lab later acquired a UNIVAC with only 2000 words of storage, requiring careful memory allocation due to varying access times, which was more of an art than a science. (Timestamp: 1327 seconds)

Richard Karp is doubtful that human-level intelligence, and thus an AI singularity, will ever be achieved. He argues that current AI successes operate within limited rules for precise tasks, far from the changing environments, emotions, intuition, and desires that characterize human cognition. He doesn't believe simply increasing computing speed will bridge this gap without a fundamental understanding of the brain's organizational principles. (Timestamp: 1591 seconds)

Combinatorial algorithms deal with discrete objects that can take on various states or values, requiring arrangement or selection to minimize a cost function or prove existence. Examples include coloring graph vertices, scheduling classes, or solving the assignment problem, often involving structures like graphs where points (vertices) are connected by lines (edges). (Timestamp: 2018 seconds)

P problems are those solvable in polynomial time (efficiently), even in the worst case. NP problems are those where a given solution can be *verified* in polynomial time, even if finding the solution itself is hard. NP-complete problems are the 'hardest' problems in NP, in the sense that if any NP-complete problem can be solved in polynomial time, then all problems in NP can be. (Timestamp: 2569 seconds)

Stephen Cook proved that the Satisfiability (SAT) problem is NP-complete, meaning any problem in NP can be re-expressed as an instance of SAT. This was a monumental step, as it implied that showing a polynomial-time algorithm for SAT would prove P=NP, unifying a vast class of seemingly disparate hard problems. (Timestamp: 3225 seconds)

The Stable Marriage Problem involves matching N boys with N girls, each with ordered preferences for the other sex, such that no two unmatched people would prefer each other over their assigned partners. A stable matching always exists and can be found by a simple algorithm where boys propose to girls, who tentatively accept better proposals, leading to a stable state where no pair wishes to 'run away together'. (Timestamp: 4396 seconds)

The Rabin-Karp algorithm uses randomization by associating a 'fingerprint' (a numerical hash value modulo a random prime) with the search word. It then efficiently computes the fingerprint for sliding windows of the longer text, checking for matches. This approach offers computational ease and a low probability of error. (Timestamp: 4840 seconds)

While worst-case analysis ensures an algorithm is *always* good, it can be misleading when it identifies a problem as hard even if it performs well in most practical instances. He gives the example of SAT solvers, which effectively tackle real-world problems with millions of variables, despite SAT being NP-complete in theory. He argues for average-case analysis where applicable. (Timestamp: 5622 seconds)

Richard Karp notes that machine learning, especially deep learning, is highly empirical, akin to how SAT solvers are evaluated. He acknowledges its huge successes across areas like image processing and robotics but highlights limitations: a lack of theoretical understanding for why networks perform well, and the difficulty in interpreting opaque network solutions to gain insight into the features driving their decisions. (Timestamp: 6654 seconds)

Richard Karp emphasizes the severe ethical problems raised by gene editing, particularly when applied to an individual's germline, which affects all descendants. He also warns against 'hubris' in assuming beneficial outcomes from knocking out specific genes, due to the unknown side effects. (Timestamp: 7048 seconds)

Richard Karp's father, an eighth-grade teacher, was at his best in the classroom, engaging with students and drawing perfect circles by hand. From this, Karp inherited a strong desire to teach, emphasizing thorough preparation (to 'the teeth') which allowed him flexibility to adapt to student questions and provide a strong model. (Timestamp: 7245 seconds)

A pivotal moment occurred during his first year of graduate school, specifically in a course on mathematical methods in operations research. He 'gobbled up the material,' scoring significantly higher than other students, which brought him to the attention of the faculty and made him realize his own academic ability, shifting him from a 'lazy student' to a dedicated researcher. (Timestamp: 7522 seconds)