01 · 计算人生
成果背后的人
理查德·卡普帮助解释了为什么许多重要优化问题难以高效地精确求解。他通过多项式时间归约，将一大类组合问题联系起来并证明其 NP 完全性。他在伯克利还研究算法与困难问题的处理方法，为区分容易处理的任务与需要不同策略的问题提供了共同框架。
理解这项贡献
理查德·卡普通过多项式时间归约，将广泛的组合问题连接起来。如果某个 NP 完全问题存在高效的精确算法，这些转换就能将其能力传递给其他问题。他还发展了网络流和其他优化任务的高效算法。
为什么重要
理解问题的结构，有助于在精确算法、近似、启发式和专用方法之间作出选择。