Dave Ishii - Problem Solving Blog

Richard Karp is considered one of the most important figures in the history of theoretical computer science, having received the Turing Award in 1985 for his research in algorithm theory. His significant contributions include the development of the Edmonds-Karp algorithm for solving the max flow problem on networks and the Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs. He is particularly famous for his landmark paper in complexity theory, "Reducibility among combinatorial problems," which proved that 21 problems were NP-complete, acting as the most important catalyst for the explosion of interest in the P versus NP problem.

https://www.youtube.com/watch?v=KllCrlfLuzs&t=580s

==

Richard Karp is a professor at Berkeley and one of the most important figures in the history of theoretical computer science.

1. He received the Turing Award in 1985 for his research in the theory of algorithms.
2. His contributions include the development of the Edmonds-Karp algorithm for solving the max flow problem on networks.
3. He also developed the Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs.
4. Karp is known for his landmark paper in complexity theory, titled "Reducibility among combinatorial problems".
5. This paper proved that 21 problems were NP-complete.
6. The paper served as the most important catalyst for the explosion of interest in the study of NP-completeness and the P versus NP problem.
7. At age 13, Karp was first exposed to plane geometry and was "wonder struck by the power and elegance of formal proofs".
8. He enjoyed the fact that pure reasoning could establish a geometric fact "beyond dispute".
9. Karp found solving puzzles in plain geometry much more enjoyable than earlier mathematics courses focused on arithmetic operations.
10. He was surprised and convinced by the ease of the proof that the sum of the angles of a triangle is 180 degrees.
11. Karp notes that he lacked three-dimensional vision and intuition for visualizing 3D objects or hyperplanes.
12. When working with tools like linear programming, he relies on algebraic properties because he lacks high-dimensional intuition.
13. When designing algorithms, he visualizes the process as an inner loop where the distance from the desired solution is iteratively reducing until the exact solution is reached.
14. He finds compelling beauty in the certainty of convergence, where the gap from the optimum point decreases monotonically.
15. Karp connects his appreciation for the orderly, systematic nature of innovative algorithms to a desire he might have had for orderly activities like woodworking.
16. He used to amuse himself by performing mental arithmetic, such as multiplying four-digit decimal numbers in his head.
17. Mathematics offers an "escape from the messiness of the real world where nothing can be proved".
18. The Assignment Problem requires finding a one-to-one matching (e.g., $N$ boys and $N$ girls) that minimizes the sum of associated costs.
19. The Hungarian Algorithm solves the Assignment Problem.
20. A key observation enabling the Hungarian Algorithm is that the optimal assignment is unchanged if a constant is subtracted from any row or column of the cost matrix.
21. The algorithm proceeds by subtracting constants from rows or columns while ensuring all elements remain non-negative, ultimately aiming for a full permutation of zeros.
22. Jack Edmonds and Karp were the first to show that the Assignment Problem could be solved in polynomial time, specifically $N^3$, improving on earlier $N^4$ algorithms.
23. As a PhD student in 1955, Karp was at the computational lab at Harvard, where Howard Aiken had built the Mark I and the Mark IV computers.
24. The Mark IV computer filled a large room, and Karp could walk around inside its rows of relays.
25. He noted that the machine would sometimes fail due to "bugs," which literally meant flying creatures landing on the switches.
26. The lab eventually acquired a Univac computer with 2,000 words of storage, which necessitated careful allocation due to varying access times.
27. Karp was primarily attracted to the underlying algorithms rather than the physical implementation of the machines.
28. He did not anticipate the future of personal computing or having computers in pockets.
29. Karp read Turing's paper on the Turing Test but felt the test was too subjective to accurately calibrate intelligence.
30. He is doubtful that algorithms can achieve human-level intelligence.
31. Karp suggests that multiplying the speed of computer switches by a large factor will not be useful until the organizational principle behind the network of switches is understood.
32. A combinatorial algorithm deals with a system of discrete objects that need to be arranged or selected to achieve some goal or minimize a cost function.
33. A graph is a set of points (vertices) where certain pairs are joined by lines (edges), often representing interconnections.
34. The maximum flow problem, which Karp worked on, involves finding the maximum rate at which a commodity (like gas, water, or information) can flow from a source to a destination through channels with capacity limits.
35. An algorithm runs in polynomial time (P) if the number of computational steps grows only as some fixed power of the size of the input (e.g., $N, N^2, N^3$).
36. Theorists generally take polynomial time as the definition of an efficient algorithm.
37. Complexity theory measures the performance of an algorithm based on its performance in the worst case.
38. NP (Non-deterministic Polynomial time) is the class of problems where, although solving the problem may be hard, verifying a potential solution can be done efficiently (in polynomial time).
39. For example, finding the largest clique is hard (NP), but checking whether a given set of vertices forms a clique is easy (P).
40. The central problem in computational complexity is whether P is equal to NP (if every problem easy to check is also easy to solve).
41. Karp strongly suspects that P is unequal to NP because centuries of intensive study have failed to find polynomial-time algorithms for many easy-to-check problems, such as factoring large numbers.
42. If P $\neq$ NP, researchers will know that for the great majority of NP-complete problems, they cannot expect to get optimal solutions and must rely on heuristics or approximations.
43. NP-complete problems are defined as the hardest decision (yes/no) problems within the class NP.
44. NP-hard problems are optimization problems that correspond to the hardest problems in the class, such as finding the largest clique rather than just deciding if one exists.
45. Stephen Cook showed that the Satisfiability problem (SAT) of propositional logic is as hard as any problem in the class P (contextually, NP).
46. Cook proved this using the abstract Turing machine, showing that any NP problem can be translated into an equivalent SAT instance.
47. Karp extended this, showing that SAT could be reduced to 21 other fundamental problems (e.g., integer programming, clique), establishing their complexity equivalence.
48. Karp considers the Stable Matching Problem (Stable Marriage Problem) to be one of the most beautiful combinatorial algorithms.
49. A matching is stable if there is no pair who would prefer to run away with each other, leaving their current partners behind.
50. An algorithm developed by Gale and Shapley ensures that a stable matching exists and can be found by having one side (e.g., boys) propose and the other side (girls) tentatively accept.
51. In the Gale and Shapley algorithm, the proposing side (the boys) ends up doing at least as well as they could in any other stable matching.
52. Karp is especially proud of the Rabin-Karp algorithm for string searching because it demonstrates the power of randomization.
53. This algorithm associates a fingerprint (a number derived using a random prime) with the word being searched.
54. The use of randomization, such as taking a random sample in an election, works well because phenomena that occur almost all the time are likely to be found via random selection.
55. Although problems like Satisfiability and the Traveling Salesman Problem are NP-hard (poor worst-case performance), practical instances arising in digital design or geometry can often be solved efficiently by specialized "sat solvers" and codes.
56. Karp studied average-case analysis by modeling random graphs, but concluded that results based on such simplistic assumptions about typical problems often lacked practical "bite".
57. He believes that if P=NP is proven, it will involve concepts and approaches that "we do not now have".
58. Karp dedicated his Turing Award lecture to the memory of his father.
59. He inherited a great desire to be a teacher from his father, remembering his ability to draw perfect circles by hand on the blackboard and engage his students.
60. His top three pieces of advice for teaching are preparation, preparation, and preparation.