NP问题/NP完全问题（NP-complete problem）如何判断是否是NP完全问题
在算法复杂度分析的过程中，人们常常用特定的函数来描述目标算法，随着变量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问题的问题类型。
判断是否是NP完全问题
1.元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变的非常慢。
2.涉及所有组合问题通常是NP完全问题
3.不能将问题分成小问题，必须考虑各种情况，这可能是NP问题
4.如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能是NP问题
5.如果问题涉及集合（如广播电台集合）且难以解决，它可能是NP完全问题
6.如果问题可转化为集合覆盖问题或商旅问题，那它肯定是NP问题
版权声明：本文为coderzjz原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。