Richard Karp
Showing 1–1 of 1 transcripts.
- Lex Fridman2h 8m
Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
Renowned theoretical computer scientist Richard Karp, recipient of the 1985 Turing Award, discusses his foundational contributions to NP-completeness theory and algorithms for string matching and stable matching while critiquing the limitations of current AI capabilities and the complexity of biological data. He addresses the unresolved P versus NP conjecture, arguing that efficient solutions likely do not exist for combinatorial problems despite their practical tractability in many real-world scenarios. The conversation further explores the ethical implications of genetic engineering, the necessity of rigorous preparation in teaching, and the distinct gap between empirical machine learning success and formal algorithmic guarantees.