关于 NP 和 NP 完整性的思考方法有很多。我会的定义开始 NP ，那么就说说 NP -hardness，终于NP -completeness。

从高层次看， P 和 NP 是问题的类别。一个问题是在 P ，如果是是或否的问题（一个
决策问题
），并有一定的算法，解决了多项式时间的问题。例如，问题“您能否在此图中从节点u到达节点v？” 属于 P，
因为您可以使用深度优先搜索来解决它。（请注意，DFS本身不在 P中 ，因为DFS是一种 算法 而不是 问题 ）。 P中
问题的另一个示例是检查序列是否按排序顺序。

如果是一个可以在多项式时间内 验证 正确答案的是或否问题（
决策问题 ），则 NP中
存在问题。例如，一个典型的 NP
问题是，在给定一组已知权重的情况下，是否可以选择正好称重某个数量k的一组权重（这称为子集和问题）。弄清楚是否存在具有该属性的一组权重可能很棘手，但是如果我要给您一组我说过的正确权重，您可以很容易地检查我是否给了您正确的权重只需将它们加起来，看看它们的总和是否为k，即可得出一组权重。
__

其原因 NP 被称为“非确定性多项式”是关于思维方式不同 NP
是考虑一个神奇的算法，可以以某种方式猜测正确答案在多项式时间的问题。也就是说，如果您可以编写允许对问题的答案进行猜测并在多项式时间内运行的算法，那么您要解决的问题就是
NP
。回到权重示例，我们可以针对问题编写如下的猜测算法。首先，以线性时间猜测哪个权重集合是正确的权重集合，然后将它们全部加起来，看它们是否总计为k。如果是这样，则报告答案为“是”。否则，说“不”。如果始终保证该程序能够做出正确的猜测，那么在给出具有解决方案的问题的任何输入后，它将始终找到一个并报告“是”，而如果没有解决方案，则它将始终在猜测中并报告“否”。

一个在计算机科学中最根本，最重要的问题，现在是已知的任何问题是否 NP 也在 P 。也就是说，如果我们可以轻松地（在多项式时间内）有效地
验证 问题的答案，我们 是否 可以始终有效地（在多项式时间内） 解决 问题？众所周知， P 中的任何问题也是 NP中
的问题，因为您可以使用多项式时间算法来生成答案，然后检查其是否正确，但是还没有人找到解决多项式 NP 中任意问题的方法。时间。

这样做的原因是，在一些问题 NP 被称为 _ NP -完全_的，这意味着（非正式）它们至少很难，因为在所有其他问题 NP
。如果我们能够有效地解决这些问题（多项式时间），那么我们就可以解决多项式时间内 NP 中的每个问题。这将是一笔不小的数目，因为 NP中
存在许多非常重要的问题，而我们目前还没有好的快速算法。这也是 P
=
NP
问题的吸引力 *
*，因为只需要一种算法就可以证明假定难以解决的一大类问题实际上可以有效解决。

更正式地说，在一个问题 NP 叫做 NP -完全如果，在多项式时间内，你可以将任何其他的任何实例 NP
问题，成问题的一个实例。上面的权重问题就是这样的问题，例如确定布尔公式是否具有令人满意的赋值，解决整数上的某些优化问题（整数规划），确定访问一组位置的最快路线（旅行推销员）），或确定如何使用最少的频率分配城市中的蜂窝塔（图形着色）。甚至确定是否有可能解决数独游戏对于任意尺寸的电路板，扫雷器和扫雷器都是
NP 完整的。

（某些问题具有后一种性质 -NP 中的任何问题都可以有效地转换为该问题-但 NP中 本身不是问题。这些问题称为 NP- Hard。）

从实践的角度来看，如果您曾经被要求解决已知为 NP完全 或 NP
困难的问题，则不要指望在任何合理的时间内找到确切的解决方案。在某些情况下，甚至不可能有效地在任何精度范围内近似求解。最好是寻找一个替代问题来尝试解决该问题，或者让自己选择一个在大多数情况下但并非所有情况下都很好的启发式解决方案。

关于DFS是 NP 完全的最初想法，只有 问题 可以是 NP 或 NP完全 。算法不能。DFS是用于解决图形可及性问题的算法-
给定图中的两个节点，是否存在从第一个到第二个的路径？这个问题在 NP中， 因为如果有一条路径很容易检查，但是（可能）不是 NP
完整的，因为我们知道我们可以使用DFS在多项式时间内解决它。

希望这可以帮助！