NP难度和NP完全问题
- 基本概念
1.1不确定的算法
1.2NP-Hard和NP-Complete类- NP-Hard问题实例
是一个想象的模型，接近的是量子计算机。
不确定算法就要尽力使算法以成功结束，选择是让图灵机自己选择。
2-6:如果有重复的就会退出
7-9:判断是否有逆序，如果有逆序也退出
只关心的是判定类的算法，即输出的结果是二值输出，除此之外没有输出语句，其他更复杂的算法可以用这个转化。
时间复杂度的度量和确定性算法也是不一样的。
合取范式和析取范式
P是属于NP的，因为确定算法是不确定算法的一个特例，那么P是否等于NP呢？（到现在也证明不了）
NP完全的问题是NP难的问题