- p问题：可以在多项式时间内找到答案。
- NP问题：可以在多项式时间内验证答案正确性的问题，但不一定能在多项式时间内找到答案。
- NP完全（NP-Complete, NPC）：一个问题属于NP完全，需要满足两个条件：
- 问题本身属于NP：也就是能够在多项式时间内验证解。
- NP归约（NP-hardness）：问题是NP中所有问题的“最难”问题，任何其他NP问题都可以通过多项式时间归约转换为该问题。
- NP-hard问题：所有的NP问题可以在多项式时间归约到它，但它不一定是一个NP问题
NP完全问题的特点
- 难解性：目前没有已知的多项式时间算法能够解决NP完全问题。
- 可验证性：一旦给出解，验证其正确性是简单的（在多项式时间内完成）。
- 普适性：如果能找到一种多项式时间算法解决某个NP完全问题，那么所有NP问题都可以在多项式时间内解决。
NP完全与P=NP问题
一个关键的开放问题是：P = NP？
- 如果P=NP，那么所有NP问题都可以通过确定性算法在多项式时间内解决。
- 如果P≠NP，则NP完全问题是确定性算法无法高效解决的。
目前，P=NP仍未被证明或否定，是计算机科学中最著名的未解难题之一。
常见的NP完全问题
- 旅行商问题（TSP, Travelling Salesman Problem）：在给定的城市集合和城市之间的路径距离中，找出一条路径，使得访问所有城市的总距离最短。
- 布尔可满足性问题（SAT, Boolean Satisfiability Problem）：判断一个布尔公式是否存在一个变量赋值，使得公式为真。
第一个被证明是NP完全的问题。 - 顶点覆盖问题（Vertex Cover Problem）：在一个图中，找出最少的顶点集合，使得每条边至少有一个端点在这个集合中。
- 集合覆盖问题（Set Cover Problem）：给定一个全集和若干集合，找到最少的集合覆盖整个全集。
- 3-彩色问题（3-Colorability Problem）：判断一个图是否可以用三种颜色对顶点进行着色，使得相邻的顶点颜色不同。
NP完全问题的应用
虽然NP完全问题很难解决，但它们在很多领域中具有重要的实际意义：
- 优化问题：如物流、调度、网络路由。
- 密码学：许多加密算法的安全性基于某些问题的NP完全性质。
- 人工智能：如规划、约束求解、机器学习中的组合优化问题。
解决NP完全问题的方法
由于没有已知的多项式时间算法，常用的处理方法包括：
- 启发式算法：使用近似解法，不保证最优解，但在实践中效果良好。
- 分支界限法：系统地探索解空间以寻找最优解。
- 动态规划：对特定问题（如旅行商问题）可以设计动态规划算法，但复杂度仍然很高。
- 近似算法：对某些问题提供接近最优解的多项式时间算法。
- 随机算法：使用随机化技术来寻找解。
总结
- NP完全问题描述了一类在理论上最难解、但易于验证的决策问题。
- 它们的研究在理论和实践中都具有深远意义。
- 是否能在多项式时间内解决这些问题（即P=NP问题）是计算机科学中的一个核心未解问题。
