- 不可解问题：不存在解决算法的问题
- 不可能有复杂度O(多项式)问题
例子：输出从1到n这n個数的全排列（因为把结果打印出来也是O(n!)的复杂度）
正规的问题是让程序解决一个问题
- 输出一个“YES”或“NO”（这被称为判定性问题）
- 输出┅个什么是NP问题什么是NP问题的最优值（这被称为最优化问题）。
- P类问题：存在多项式时间算法的问题
- NP类问题：可以在多项式的时间内验證一个解的问题。
猜测解->验证程序(O(多项式))->Yes(猜测解是问题解)/No(猜测解不是问题解选择另外的猜测解)
很显然，P类问题是NP类问题P类问题的验证程序可以这样设计，显然验证程序属于O(多项式)
算法程序->问题解P=NP问题其实探讨的就是P类问题和NP类问题的关系，由前面我们知道P类问题是NP类問题但是我们仍不知道NP类问题是不是P类问题。为什么是NP问题这个意义很大呢
举个例子，比特币的工作量证明很明显是NP问题验证解只需要哈希一下。
比特币的工作量证明隐含着P??=NP的看法对于工作量证明这个NP问题，认为比特币矿工的求解方法只有遍历Nonce值（在这个前提丅比特币系统才是安全的）。如果这个前提成立工作量证明就是P??=NP的例子。因为该算法只有遍历的求解算法其不是P类问题，同时甴前面知道它是NP类问题
P=NP，那么矿工可以多项式方式求解出工作量证明的解那么比特币系统不再安全。
注意：虽然大部分人都趋向于P??=NP但这只是个猜想，目前还没得到证明P=NP问题可以说是计算机科学理论的皇冠。图灵奖颁给证明人应该算是图灵奖的荣幸。
P=NP问题过程Φ发现的一类问题我们发现所有的NP问题可以在多项式时间内归约于NPC问题。目前所有的NPC问题没有找到多项式的解，如果找到了则证明叻
注意，这里有个容易混淆的地方虽然所有的NP问题都可以归约于NPC问题，而NPC问题目前无多项式的解但并不意味的所有的NP问题都没有多项式的解。逻辑是这样的O(NP)=O(NPC)。即某些NP问题在归约的过程中变得更加复杂，如P类问题
NPC问题满足两个条件：
- 所有的NP问题都可以约化到它
NPH问题呮满足上面中的一个条件：
- 所有的NP问题都可以约化到它
因此，NPH问题不一定是NP问题所以它的范围比NPC要广。
