什么是计算机科学的NP完整？
什么是NP完全问题？ 为什么这是计算机科学中的一个重要话题？
NP表示非确定性多项式时间。
这意味着可以使用非确定性图灵机（像普通图灵机，但也包括非确定性“select”函数）在多项式时间内解决问题。 基本上，一个解决scheme必须在多时间内进行testing 。 如果是这种情况，并且已知的NP问题可以通过修改后的input来解决给定的问题（NP问题可以归结为给定的问题），那么问题是NP完全的。
从NP完全问题中解决的主要问题是不能用任何已知的方法在多项式时间内求解。 NP-Hard / NP-Complete是一种表示某些类别的问题在现实时间不可解的方式。
编辑：正如其他人所指出的，NP-Complete问题通常有近似的解决scheme。 在这种情况下，逼近解通常给出一个使用特殊符号的近似界，它告诉我们近似值是多么接近。
什么是NP ？
NP是所有可以在多项式时间内validation “是”答案的所有决策问题的集合（O（n k ），其中n是问题的大小， k是一个恒定）由一个确定性的图灵机 。 多项式时间有时用作快速或快速的定义。
什么是P ？
P是确定性图灵机可以在多项式时间内解决的所有决策问题的集合。 由于它们可以在多项式时间内求解，因此也可以在多项式时间内validation。 所以P是NP的一个子集。
什么是NP-Complete ？
NP中的问题x也是NP-Complete 当且仅当 NP中的每个其他问题都可以快速地（即在多项式时间内）转换成x。
换一种说法：
- x在NP中，而
- NP中的每一个问题都可以归结为x
那么NP-Complete如此有趣的原因在于，如果任何一个NP-Complete问题都要很快得到解决，那么所有的NP问题都可以很快得到解决。
又见post什么是“P = NP？”，为什么这么着名？
什么是NP-Hard ？
NP-Hard是NP中最难的问题。 请注意，NP-Complete问题也是NP难题。 然而，并不是所有的NP难题都是NP（甚至是决策问题），尽pipe以NP为前缀。 NP-NP中的NP不等于非确定性的多项式时间 。 是的，这是令人困惑的，但它的使用是根深蒂固的，不太可能改变。
NP-Complete意味着非常具体的东西，你必须小心，否则你会得到错误的定义。 首先，NP问题是一个是/否的问题
- 对于每个问题的实例，有一个“是”的答案，答案是“是”，或者（等价地）是多项式时间的certificate。
- 存在一个多项式时间algorithm（可能使用随机variables），如果问题的实例的答案是“是”，并且如果100％的时间是“否”，则具有回答“是”的非零概率答案是不。” 换句话说，该algorithm必须具有小于100％的假阴性率并且没有误报。
一个问题X是NP完全的如果
- X在NP中，
- 对于NP中的任何问题Y，从Y到X有一个“减less”：一个多项式时间algorithm，将Y的任何实例转换为X的一个实例，这样当且仅当Y实例的答案为“是”如果答案X实例是“是”。
如果X是NP-完全的并且存在能够正确解决所有X的实例的确定性多项式时间algorithm（0％假阳性，0％假阴性），那么NP中的任何问题都可以用确定性多项式 – 时间（通过减less到X）。
到目前为止，还没有人提出这样一个确定性的多项式时间algorithm，但是没有人certificate一个algorithm是不存在的（任何人都可以做到这一点，那就是P = NP问题 ）。 这并不意味着你不能解决一个NP-Complete（或NP-Hard）问题的特定实例。 这只是意味着你不可能拥有能够在一个问题的所有实例上可靠工作的东西，就像你可以可靠地对一个整数列表进行sorting一样。 你可能会想出一个在NP-Hard问题的所有实际情况下都能很好地工作的algorithm。
如果你正在寻找一个NP完全问题的例子，那么我build议你看看3-SAT 。
基本的前提是你有一个expression式的连接规范forms ，这是一种说法，你有一系列的expression式连接的ORs都必须是真实的：
(a or b) and (b or !c) and (d or !e or f) ...
3-SAT问题是find一个满足expression式的解决scheme，每个ORexpression式恰好有3个布尔值匹配：
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
这个解决scheme可能是（a = T，b = T，c = F，d = F）。 然而，在多项式时间的一般情况下，没有发现可以解决这个问题的algorithm。 这意味着解决这个问题的最好办法是做一个基本的蛮力猜测和检查，并尝试不同的组合，直到find一个可行的组合。
3-SAT问题的特别之处在于，任何NP完全问题都可以归结为3-SAT问题。 这意味着如果你能find一个多项式时间algorithm来解决这个问题，那么你可以得到100万美元 ，更不用说世界各地的计算机科学家和math家的尊重和钦佩。
NP-Complete是一类问题。
P类包含那些在多项式时间可解的问题。 例如，对于某个常数k，可以用O（ nk ）来解决，其中n是input的大小。 简而言之，你可以编写一个在合理时间内运行的程序。
类NP由可在多项式时间内validation的那些问题组成。 也就是说，如果我们给出一个潜在的解决scheme，那么我们可以检查给定的解决scheme在多项式时间是否正确。
一些例子是布尔可满足性（或SAT ）问题，或哈密顿周期问题。 在NP中已知有很多问题。
NP-Complete意味着问题至less与NP中的任何问题一样困难。
因为已经certificateNP中的任何问题都可以转化为NP-complete中的另一个问题，所以对计算机科学来说非常重要。 这意味着任何一个NP完全问题的解决scheme都是NP问题的解决scheme。
许多安全algorithm取决于NP难题存在的已知解决scheme。 如果find解决scheme，这肯定会对计算机产生重大影响。
基本上这个世界的问题可以被归类为
1）不可解决的问题2）难以解决的问题3）NP问题4）P问题
1）第一个问题没有解决办法。 2）第二是需要指数时间（即上面的O（2 ^ n））。 3）第三个被称为NP。 4）第四个是容易的问题。
P：指的是多项式时间问题的解决scheme。
NP：指多项式时间还没有find解决scheme。 我们不确定没有多项式时间解决scheme，但是一旦您提供解决scheme，就可以在多项式时间中validation此解决scheme。
NP完成：在多项式时间中我们还没有find解决scheme，但可以在多项式时间中进行validation。 NP中的NPC问题是比较困难的问题，所以如果能certificate我们有P解决NPC问题的话，那NP问题就可以在P解中find。
NP Hard：指多项式时间还没有find解决scheme，但是它确定无法在多项式时间中validation。 NP困难问题超过NPC难度。
老实说， 维基百科可能是寻找答案的最好的地方。
如果NP = P，那么我们可以比我们以前想象的更快地解决非常困难的问题。 如果我们在P（多项式）时间只解决一个NP-Complete问题，那么它可以应用于NP-Complete类别中的所有其他问题。
这是一类问题，我们必须模拟一切可能性，以确保我们有最佳的解决scheme。
对于一些NP-Complete问题，有很多很好的启发式方法，但是它们只是一个受过教育的猜测。
我们需要分离algorithm和问题。 我们编写algorithm来解决问题，并以一定的方式进行扩展。 虽然这是一个简化，但如果缩放足够好，我们用“P”标记一个algorithm，如果不是，则标记为“NP”。
了解我们正在尝试解决的问题，而不是我们用来解决问题的algorithm是有帮助的。 所以我们要说的是，所有具有缩放algorithm的问题都是“在P中”。 那些具有较差缩放algorithm的是“在NP中”。
这意味着很多简单的问题也是“在NP中”，因为我们可以编写错误的algorithm来解决简单的问题。 知道NP中的哪些问题是非常棘手的问题将是一件好事，但我们不只是想说“这是我们还没有find一个好的algorithm”。 毕竟，我可以想出一个问题（称为X），我认为需要一个超级惊人的algorithm。 我告诉全世界，我能想出的最好的algorithm来解决X的缩放问题，所以我认为X是一个非常棘手的问题。 但是明天，也许有人比我更聪明的发明了一种解决X的algorithm，并且在P中。所以这不是一个很好的定义。
同样，在NP中有很多问题没有人知道一个好的algorithm。 所以如果我能certificate X是某种问题的话，那么也可以用一个好的algorithm来解决X， 也可以用一些迂回的方法给NP中的其他问题给出一个好的algorithm。 那么现在人们可能会更确信X是一个真正棘手的问题。 在这种情况下，我们称之为X NP-Complete。
离散math有一个非常好的讲座 ，讲解了一个NP完全问题。
前50分钟主要是布尔代数。 因此，如果您只对P，NP，NP-完备性，布尔可满足性问题和约简的概念感兴趣，就跳到第53分钟的开头。
以上NP完全问题的定义是正确的，但是我认为我可能对其哲学重要性抒情，因为没有人解决这个问题。
几乎所有你遇到的复杂问题都将是NP完成。 对于这个class级来说，有一些非常基础的东西，而这些东西在计算上似乎与容易解决的问题有所不同。 他们有自己的味道，认识他们并不难。 这基本上意味着任何适度复杂的algorithm都不可能完全解决 – 调度，优化，打包，覆盖等。
但是，如果遇到的问题是NP完成，并不是全部都会丢失。 有一个庞大的技术领域，人们在这里学习近似algorithm，这将为您提供接近解决NP完全问题的保证。 其中一些是非常有力的保证 – 例如，3sat，你可以通过一个非常明显的algorithm得到7/8的保证。 更好的是，在现实中，有一些非常强的启发式方法，这些方法在为这些问题提供很好的答案（但是不能保证！）方面很出色。
请注意，两个非常着名的问题 – 图同构和因式分解 – 并不知道是P还是NP。
我曾经听到过一个解释，那就是：“NP-完整性可能是algorithm研究中更神秘的思想之一。”NP“代表”非确定性多项式时间“，是所谓复杂类的名称，哪些问题可以归属，关于NP复杂类的一个重要问题就是这个类中的问题可以用一个多项式时间algorithm来validation ，举个例子，考虑一下计算问题，假设一个表上有一堆苹果。问题是“有多less苹果？”给你提供一个可能的答案，8.你可以用多项式的时间来validation这个答案，使用algorithm来计算苹果计数苹果发生在O（n） （这是Big-oh符号）的时间，因为它需要一个步骤来计算每个苹果，对于n个苹果，你需要n个步骤，这个问题在NP复杂等级中。
如果一个问题可以certificate是NP-Hard并且可以在多项式时间内validation ，则问题被归类为NP-complete 。 不要过于深入地讨论NP-Hard，只要说没有find多项式时间解的某些问题就足够了。 也就是说，它需要像ñ！ （n阶乘）步骤来解决它们。 但是，如果给出NP-Complete问题的解决scheme，则可以在多项式时间内对其进行validation。
一个NP完全问题的典型例子是旅行推销员问题。“
作者：ApoxyButt来自： http ://www.everything2.com/title/NP-complete
NP完全问题是在多项式时间内任何其他NP问题可以减less的一组问题，其解决scheme仍然可以在多项式时间validation。 也就是说，任何NP问题都可以转化为任何NP完全问题。 – 非正式地说，一个NP完全问题是一个NP问题，至less和NP中的任何其他问题一样“困难”。
NP问题： –
- NP问题是可以在非确定性多项式时间内解决的问题。
- 非确定性algorithm分两个阶段运行。
- 非确定性猜测阶段&&非确定性validation阶段。
Np问题的types
- NP完整
- NP难
NP完成问题： –
1决策问题A如果具有以下两个属性，称为NP完整性：
- 它属于NP类。
- NP中的其他任何问题都可以在多项式时间内转化为P.
一些例子： –
- 背包问题
- 分组总和问题
- 顶点覆盖问题
NP问题是可以在多项式时间中创buildvalidation解的计算机algorithm的问题。
一个NP完全问题是NP，但是如果你可以用多项式时间（称为P）解决它，那么所有NP问题都是P.
所以得到破解'。
