卡普的二十一个NP完全问题为何重要

数码应用

1971年，斯蒂芬·库克证明布尔可满足性问题具有NP完全性，为计算复杂度研究提供了起点。1972年，理查德·卡普在《组合问题之间的可归约性》中进一步证明二十一个重要组合与图论问题具有同类性质。

这些问题包括0—1整数规划、团、顶点覆盖、集合覆盖、哈密顿回路、三文字可满足性及图着色等。它们表面上处理的对象不同，却能通过归约建立联系，使研究者不必为每一个难题孤立寻找复杂度证明。

归约的方向很重要：把一个已知困难问题转化为另一个问题，才有助于说明后者至少包含相应难度，同时还要满足NP类别要求。卡普的成果扩大了NP完全问题的范围，也推动P与NP关系的研究。不过，列入这份名单并不等于已经证明这些问题绝不可能存在多项式时间算法。

资料依据：维基百科《卡普的二十一個NP-完全問題》及该页贡献者（修订记录）。本文重组论述并改写表达；依Creative Commons Attribution-Share Alike 4.0提供。