NP问题，NP完全问题（NPC），NPhard问题
一、相关概念
P
能在多项式时间内解决的问题
一个问题可以在多项式（O(n^k)）的时间复杂度内解决. 例如：n个数的排序（不超过O(n^2)）
形如f(x)=an·x^n+an-1·x^(n-1)+…+a2·x^2+a1·x+a0的函数，叫做多项式
NP
不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题.
例如：典型的子集求和问题,给定一个整数集合求是否存在一个非空子集它的和为零。如给定集合s={-1,3,2,-5,6}，很明显子集{3,2,-5}能满足问题，并且验证该解只需要线性时间复杂度就能被证实。
NPC
NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题，即解决了此NPC问题，所有NP问题也都得到解决。
如果所有NP问题都能在多项式时间内转化为A，则称A为NPC问题。
NPC是NP的子集。
例如： 求哈密顿回路是个NPC问题，它可以在多项式时间内验证。
NP hard
NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)
问题A不一定是一个NP问题，但所有的NPC问题都可以在多项式时间内转化为A，则称A为NPH问题。
二、四者联系的图形表示
https://zhuanlan.zhihu.com/p/102362515
0/1背包判定问题是NPC问题；
举例分析：旅行商问题（TSP）
决策版本
- 问题描述：给定一个权重上限 ( k )，判断是否存在一条路径，满足路径总权重不超过 ( k )。
- 分类：这是一个 NPC 问题。
- 原因：
- 属于 NP 类：可以在多项式时间内验证解。例如，给定一条具体路径，只需计算路径总权重并判断是否小于等于 ( k )。
- NP 完全性：所有其他 NP 问题都可以归约为该问题。
优化版本
- 问题描述：寻找一条路径，使得路径的总权重最小。TSP 的优化版本是寻找一个哈密顿回路（即经过图中每个顶点一次且仅一次的回路），使得路径的总权重最小。
- 直接枚举所有可能的哈密顿回路，选择总权重最小的路径。时间复杂度是O(n!)
- 分类：这是一个 NPH 问题。
- 原因：
- 不一定属于 NP 类：因为解的验证可能需要求解全局最优值，而这通常无法在多项式时间内完成。
- 更一般化：优化问题的求解比决策问题更困难，其复杂性至少与 NPC 问题一样高。