从组合问题出发
理查德·卡普（Richard M. Karp）是研究算法与计算复杂性的计算机科学家。他于1959年获得哈佛大学应用数学博士学位，随后在IBM研究部门工作，后来长期任教于加州大学伯克利分校。他关注的核心问题既包括怎样找到有效算法，也包括为什么一些问题难以求解，不能仅以Rabin–Karp算法概括其研究。
在IBM时期，卡普与雷·米勒、迈克尔·赫尔德等人研究并行计算模型与组合优化。与杰克·埃德蒙兹交流，使多项式时间这一衡量算法效率的尺度成为其研究的重要线索。这里的效率是随输入规模增长的渐近界限，并非某台机器一次运行的快慢。
用归约联系不同难题
1972年的《组合问题之间的可归约性》承接斯蒂芬·库克的可满足性定理，展示了一组经典组合问题的NP完全性。归约把问题甲的实例在多项式时间内变成问题乙的实例，并保持“是”与“否”的答案；若乙能高效求解，甲也因此能高效求解。
论文把合取范式的可满足性归约为团问题：为各子句中的文字出现建立顶点，只连接来自不同子句且不互相矛盾的文字。若有k个子句，寻找大小为k的团，就对应于从每个子句选出一个能共同成立的文字。图的构造把逻辑约束转成了两两相容的邻接关系。
NP完全性不是已证明不存在多项式算法，也不表示所有实例同样困难。它说明一类问题的最坏情形复杂性相互联系；卡普的贡献在于把这种联系落实到熟悉的图论、覆盖与调度等问题，而不是创立了全部复杂度理论。
与拉宾合作的字符串指纹
卡普与迈克尔·拉宾在1987年共同发表随机化模式匹配论文。其基本办法是先给模式串与文本窗口计算较短的数值指纹，再比较指纹；窗口向前滑动时，可以利用前一窗口的结果更新计算，不必每次从头处理整个窗口。
指纹相同不保证字符串相同，因为不同字符串可能碰撞。论文讨论了不同处理方式：有的方案在指纹匹配后逐字符核实，有的允许可控制的极小误差概率。因此，随机化、正确性和运行时间必须连同具体方案说明。这是两位作者的共同研究，也不是NP完全性归约的另一名称。
参考：[3]
算法分析与研究范围
卡普还与埃德蒙兹研究网络流，与约翰·霍普克罗夫特研究二分图匹配，后来转向概率分析和计算生物学。对随机输入的平均表现、算法主动使用随机数的表现，以及任意输入下的最坏界限，是相互关联却不等同的问题。
这些工作体现了他在寻找有效算法与辨认困难结构之间的往返。研究历程也包含合作者、学生和机构的持续参与：把各种冠有“Karp”的成果统一说成一种算法，既会抹去问题差异，也会模糊共同贡献。