概念NP-complete / NPC
NP完全
计算复杂性理论中的一类问题，属于NP类且所有NP问题都可以在多项式时间内归约到它，通常需要指数级搜索或启发式近似。
时间轴 (近 90 天)
10月22日
P2NPCBench 是一个新的基准测试，包含 12 组问题家族，每组由一个 NP 完全问题和一个表面表述相同的多项式时间可解问题组成。
待验证50%
10月22日
NP 完全问题是 NP 类中最难的一类，任何 NP 问题都可以在多项式时间内归约到它；经典例子包括旅行商问题的判定版本、布尔可满足性问题（SAT）和图的 3-着色问题。
待验证50%
9月18日
即便对于多项式时间可识别的图类，其对应的夹心问题也可能是 NP 完全的
待验证50%
9月2日
Cook-Levin定理证明了SAT问题是NP完全的
待验证50%