Graphs and Complexity
Richard discusses the fascinating relationship between graphs and logical equations, highlighting how various hard problems share the same expressive power. He explains the distinction between NP complete and NP hard problems, emphasizing that while they can express each other, their computational complexities may differ. The conversation dives deep into the implications of these classifications and their significance in understanding problem-solving in computer science.In this clip
From this podcast
Lex Fridman Podcast
Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
Related Questions
Can mathematics solve complex problems as discussed in the episode Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111 and the clip NP and Satisfiability?
Can mathematics solve complex problems as discussed in the episode Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111 and the clip P vs NP Insights?