1985 · 理论与算法

绘制计算难度的地图

归约显示，许多实际问题有着相同的困难核心。

理查德·卡普

1985图灵奖

视觉指南

奖项，化为图解

阅读图解文字

理解问题的结构，有助于在精确算法、近似、启发式和专用方法之间作出选择。

困难性结论针对一般输入类别；很多特殊情形仍然能够高效求解。

01 · 核心想法

理查德·卡普通过多项式时间归约，将广泛的组合问题连接起来。如果某个 NP 完全问题存在高效的精确算法，这些转换就能将其能力传递给其他问题。他还发展了网络流和其他优化任务的高效算法。

理解问题的结构，有助于在精确算法、近似、启发式和专用方法之间作出选择。

02 · 人物

理查德·卡普帮助解释了为什么许多重要优化问题难以高效地精确求解。他通过多项式时间归约，将一大类组合问题联系起来并证明其 NP 完全性。他在伯克利还研究算法与困难问题的处理方法，为区分容易处理的任务与需要不同策略的问题提供了共同框架。

03 · 延伸阅读

本站原创讲解依据官方获奖记录。领域标签用于编辑导航。