完成计算机科学？
什么是NP完全问题？ 为什么它是计算机科学中如此重要的话题？
NP表示非确定性多项式时间。
这意味着该问题可以在使用非确定性图灵机（如普通图灵机，但也包括非确定性“选择”功能）的多项式时间内解决。 基本上，解决方案必须在多时间内进行测试。 如果是这种情况，并且已知的NP问题可以通过修改后的输入使用给定的问题来解决（NP问题可以归结为给定问题），那么问题就是NP完成。
从NP完全问题中解决的主要问题是它不能用任何已知的方式在多项式时间内求解。 NP-Hard / NP-Complete是一种显示某些类别的问题在现实时间不可解的方式。
编辑：正如其他人所指出的，NP-Complete问题通常有近似解决方案。 在这种情况下，近似解通常使用特殊符号给出一个近似界，它告诉我们近似值是多么接近。
什么是NP？
NP是所有可以在多项式时间内验证 “是”答案的决策问题集合（O（nk），其中n是问题规模，k是一个常数）由一个确定性的图灵机。 多项式时间有时用作快速或快速的定义。
什么是P？
P是确定性图灵机在多项式时间内可以解决的所有决策问题的集合。 由于它们可以用多项式时间求解，因此它们也可以用多项式时间来验证。 因此P是NP的一个子集。
什么是NP-Complete？
当且仅当NP中的每个其他问题都可以快速（即在多项式时间内）转换为x时，NP中的问题x也在NP-Complete中。
换一种说法：
那么，NP-Complete如此有趣的原因是，如果任何一个NP-Complete问题都要很快解决，那么所有NP问题都可以很快解决。
另请参阅帖子什么是“P = NP？”，以及为什么这是一个着名的问题？
什么是NP-Hard？
NP-Hard的问题至少与NP中最难的问题一样困难。 请注意，NP-Complete问题也是NP难题。 然而，并非所有的NP难题都是NP（甚至是决策问题），尽管以NP作为前缀。 那就是NP-NP中的NP并不意味着非确定性的多项式时间。 是的，这是令人困惑的，但它的用法是根深蒂固的，不太可能改变。
NP-Complete意味着非常具体的东西，你必须小心，否则你会得到错误的定义。 首先，NP问题是一个是/否的问题
一个问题X是NP完全的，如果
如果X是NP-完全的并且存在能够正确解决所有X的实例的确定性多项式时间算法（0％假阳性，0％假阴性），那么NP中的任何问题都可以用确定性多项式 - 时间（通过减少到X）。
到目前为止，没有人提出这样一个确定性的多项式时间算法，但没有人证明没有人存在（对于任何人都可以做的任何一项都有一百万美元：这是P = NP问题）。 这并不意味着您无法解决NP-Complete（或NP-Hard）问题的特定实例。 它只是意味着你不能拥有能够在问题的所有实例上可靠工作的东西，就像你可以可靠地对整数列表进行排序一样。 你可能会想出一个在NP-Hard问题的所有实际情况下都能很好地工作的算法。
链接地址: http://www.djcxy.com/p/6801.html