NP完全问题：不确定性图灵机在P时间内能解决的问题,如何证明?

如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题.
NP问题是指可以在多项式的时间里验证一个解的问题.NP问题的另一个定义是,可以在多项式的时间里猜出一个解的问题.
NP-Hard问题：所有的NP问题都能规约到它,但它不一定是NP问题.
NP完全问题,也就是多项式复杂程度的非确定性问题.

NP里面的N,不是Non-Polynomial的N,是Non-Deterministic,P代表Polynomial倒是对的.NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题.什么是非确定性问题呢?有些计算问题是确定性的,比如...

的问题.问题就在这个问号上,到底是NP等於P,还是NP不等於P.这个奖还没有人拿到,也就是说,NP问题到底是Polynomial,还是Non-Polynomial,尚无定论.NP里面的N,不是Non-Polynomial的N,是Non-Deterministic,P代表Polynomial...

在算法复杂度分析的过程中,人们常常用特定的函数来描述目标算法,随着变量n的增长,时间或者空间消耗的增长曲线,近而进一步分析算法的可行性（有效性）.
引入了Big-O,Big-Ω,来描述目标算法的上限、下限复杂度函数.
用Big-Θ描述和目标函数同序的复杂度函数,即由Big-Θ既是上限也是下限.
常常用到如下时间复杂度函数标度
1, log n, n, n log n, n^2, 2^n, n!
通常将具有n^x,x为正整数形式的时间复杂度函数称为多项式复杂度.通常认为具有多项式时间复杂度的算法是容易求解的.超过多项式时间复杂度,算法增长迅速,不易求解.
下图将展示NP和NP完全问题在所有问题中的位置.
通常问题分为 可解决（Solvable） 和 不可解决（Unsolvable）.
可决绝问题又可以分为 易解决（Tractable）、不易解决（Intractable）和不确定是否容易解决（NP）
可解决（Solvable）是指存在算法能够解决的问题
不可解决（Unsolvable）是指不存在解决该问题的算法,如The Halting Problem.
易解决（Tractable）,即P问题,是指具有最坏时间复杂度为多项式时间的算法能够解决的问题
不易解决（Intractable）是指不存在最坏时间复杂度为多项式时间的算法能够解决的问题
不确定是否容易解决（NP）,还未被证明是否存在多项式算法能够解决这些问题,而其中NP完全问题又是最有可能不是P问题的问题类型.