无论是P的问题= NP也许是最著名的所有计算机科学。 这是什么意思？ 为什么它这么有趣？
哦，还有额外的信用，请发表的声明的真或假的证明。 :)
Answer 1:
P代表多项式时间。 NP代表非确定性多项式时间。
定义：
多项式时间意味着该算法的复杂度是O（n ^ k），其中n是数据的大小（在一个列表中的元素的数目例如进行排序），并且k是常数。
复杂性是在将采取操作的数量测量，如数据项的数目的函数的时间。
操作是任何有意义的，因为对于一个特定的任务的基本操作。 用于排序的基本操作是比较。 对于矩阵乘法的基本操作是两个数字的乘法。
现在的问题是，什么是确定性与不确定性均值。 有一个抽象的计算模型，一个假想的计算机称为图灵机（TM）。 此机具有有限数量的状态，和一个无限的磁带，它具有分立单元到其中的符号的有限集合可以被写入和读出。 在任何给定时间，TM是它的一个状态，它正在考虑在磁带上的特定细胞。 根据它从该小区读取，它可以写一个新的符号到该小区，向前或向后移动磁带一个单元，并进入不同的状态。 这就是所谓的状态转变。 令人吃惊的是，通过精心构建的状态和转移，你可以设计一个TM，这相当于可写入任何计算机程序。 这就是为什么它被用来作为证明什么电脑可以和不可以做的事情的理论模型。
有两种TM年代，这里引起我们的关注：确定性与不确定性。 确定性TM仅具有从每个状态，它是读取关闭磁带的每个符号一个过渡。 非确定性TM可以具有几个这样的过渡，即，它能够同时检查几个可能性。 这有点像产卵多线程。 不同的是，非确定性TM可以产卵许多这样的“线程”，因为它想要的，而真实的计算机上可以在一个时间（等于CPU的数量）来执行仅线程的特定数目。 在现实中，电脑基本上都是有限的磁带确定性的TM。 在另一方面，非确定性TM不能物理实现，除了可能有一台量子计算机。
它已被证明可以由非确定性TM可以解决任何问题可以用一个确定性TM来解决。 但是，目前还不清楚它会花费多少时间。 语句P = NP意味着，如果一个问题需要多项式时间上的非确定性TM，则一个可以构建确定性TM这也将解决同样的问题在多项式时间。 到目前为止，没有人已经能够证明这是可以做到的，但没有人能够证明它不能这样做，无论是。
NP完全问题是指NP问题X，使得任何NP问题Y可以通过多项式减少降低到X。 这意味着，如果有人曾经与一个多项式时间解决NP完全问题出现了，这也将给出一个多项式时间解决任何NP问题。 因此，将证明P = NP。 反之，如果有人是为了证明将P！= NP，那么我们就可以肯定，有没有办法解决在多项式时间的NP问题的传统计算机上。
NP完全问题的例子是找到一个真值赋值，将使含n个变量的布尔表达式真正的问题。
对于在实践中时刻，需要多项式时间上的不确定性TM任何问题，只能在指数时间上做确定性TM或传统的计算机上。
例如，为了解决真值赋值问题的唯一方法是尝试2 ^ N的可能性。
Answer 2:
- 一个是或否的问题属于P（P olynomial时间），如果答案可以在多项式时间来计算。
- 一个是或否的问题是NP（N上确定性P olynomial时间），如果是的回答可以在多项式时间进行验证 。
直观地说，我们可以看到，如果一个问题是P，那么它是在NP。 鉴于P中的一个问题潜在的答案，我们可以通过简单地重新计算答案验证答案。
不太明显，而且更加难以回答，是在NP的所有问题是否P中。 难道我们可以验证在多项式时间内答复的事实意味着我们可以计算在多项式时间这个问题的答案？
有大量的已知是NP -完整的重大问题（基本上，如果有的话这些问题都被证明是P，那么所有的 NP问题都被证明是P）。 如果P = NP，那么所有这些问题将被证明具有有效（多项式时间）溶液。
大多数科学家相信， 磷 ！= NP。 但是，没有证据尚未建立或者P = NP或P！= NP。 如果有人提供了两种猜想的证明， 他们将赢得100万$ 。
Answer 3:
为了让我能想到的最简单的答案：
假设我们有需要一定数量的输入，并具有各种可能的解决方案，这可能会或可能不会解决这个问题给定输入的问题。 在一个谜杂志逻辑谜题将是一个很好的例子：在输入的条件是（“乔治并不住在蓝或绿房子”），以及潜在的解决方案是语句列表（“乔治·住在黄色房子，成长豌豆，并拥有狗“）。 一个著名的例子就是旅行商问题：给定的城市名单，并与时俱进地从任何城市的任何其他，和时间限制，一个潜在的解决办法是在销售员访问它们的顺序城市列表，并如果旅行时间的总和小于时限它会工作。
这样的问题是NP如果我们能有效地检查潜在的解决方案，看看它是否工作。 例如，假定城市的列表业务员为了参观，我们可以添加了次城市之间的每个行程，并很容易地看到，如果它是下的时间限制。 一个问题是P中如果我们能有效地找到解决的办法如果存在的话。
（高效，在这里，有一个精确的数学意义。实际上，这意味着大的问题都不是不合理难以解决。当一个可能的解决方案搜索，低效的方法是列出所有可能的潜在的解决方案，或者说接近，而一个有效的方式将需要寻找一组有限得多。）
因此，P = NP问题可以表述是这样的：如果你能验证排序的问题的解决方案上面描述的效率，你可以找到一个解决方案（或证明都没有）有效？ 答案显然是“你为什么能？”，这是相当多的地方无论今天站立。 没有人能够证明这一点的一种方式或其他，并且困扰了许多数学家和计算机科学家。 这就是为什么任何人谁能够证明该解决方案是向上从克莱普尔基金的200万美元。
我们一般认为P不等于NP，有找到解决办法没有通用的方法。 如果事实证明，P = NP，很多事情会改变。 例如，密码将变得不可能，有了它任何形式的互联网上的隐私或可验证性。 毕竟，我们能够有效地采取加密文本和密钥及产生的原始文本，所以如果P = NP，我们可以有效地找到不知道这一点，事前的关键。 密码破解将变得微不足道。 在另一方面，有整个班级的规划问题和资源分配的问题，我们可以有效地解决。
你可能听说过的说明NP完全问题。 NP完全问题是一个NP是（当然），并拥有这个有趣的特性：如果是在P，每一个NP问题，所以P = NP。 如果你能找到一种方法，有效地解决旅行商问题，或从惑杂志逻辑难题，可以有效地解决NP什么。 NP完全问题是，在某种程度上，排序最困难的NP问题。
所以，如果你能找到任何NP完全问题的有效通用的解决方案技术，或证明没有这样的存在，名利是你的。
Answer 4:
从我的卑微知识的简短摘要：
有一些简单的计算问题（例如，查找在图中，两个点之间的最短路径），由此可以计算非常快（O（N ^ k），其中n是输入的大小，而k是一个常数（在图的情况下，它的顶点或边））的数量。
其他的问题，比如寻找跨越每个顶点在图中的路径，或正从公钥RSA私钥是很难（O（E ^ N））。
但是CS说话告诉的问题是，我们不能“转换”非确定性图灵机的确定性之一，我们可以，但是，变换非确定性有限自动机（如正则表达式解析器）为确定性的人（当然，你可以，但该机的运行时间将需要很长时间）。 也就是说，我们必须想尽一切可能的途径（通常是智能CS教授可以排除一些的）。
这很有趣，因为没有人甚至有解决方案的任何想法。 有人说这是真的，有人说这是假的，但没有达成共识。 另一个有趣的事情是，一个解决办法是有害的公钥/私钥加密（如RSA）。 你可以打破他们一样容易产生RSA密钥是现在。
而且这是一个非常鼓舞人心的问题。
Answer 5:
没有多少，我可以添加到什么以及为什么P的=？这个问题的NP一部分，但在关于证明。 不仅将证明是值得一些额外的信贷，但它会解决的一个千年问题 。 一个有趣的调查是最近进行和公布的结果（PDF）是绝对值得一读的问候证明的主题。
Answer 6:
首先，定义如下：
一个特别的问题是在p如果可以计算在时间少于一溶液
n^k一些k，其中n是输入的大小。 例如，排序可以在完成n log n小于n^2，所以排序是多项式时间。一个问题是在NP如果存在
k使得存在至多存在大小的溶液n^k它可以至多时刻验证n^k。 采取图的3-着色：给定的曲线图，3-着色的具有大小（顶点，颜色）对的列表O(n)也可以在时间验证O(m)（或O(n^2)）所有邻居是否有不同的颜色。 因此，一个图形是3-着色仅当有一个短的和容易核查的溶液。
NP的等效定义是“问题可以解决由P中olynomial时间A N ondeterministic图灵机”。 虽然，告诉你哪里的名字从何而来，它不会给你一个什么样的NP问题都喜欢同样的直观感受。
需要注意的是，P是NP的一个子集：如果你能找到在多项式时间的解决方案，有可以在多项式时间内验证的解决方案 - 只是检查给出的解决方案是等于一个你可以找到。
为什么这个问题P =? NP P =? NP有意思吗？ 要回答这个问题，首先需要看什么NP完全问题。 简单地说，
- 一个问题L是NP完全如果（1）L是在P，和（2），其解决了L可被用来解决任何NP问题L”的算法; 也就是说，给定L的实例“你可以创建L的实例有当且仅当L的实例的解决方案”有一个解决方案。 从形式上来讲，每一个问题L”在NP 还原为L.
需要注意的是L的实例必须是多项式时间计算，并具有多项式的大小，在L'的大小; 这样一来，解决在多项式时间的NP完全问题给了我们一个多项式时间内解决所有 NP问题。
这里有一个例子：假设我们知道图的3着色是一个NP难问题。 我们要证明，在决定布尔公式的满足性是NP难问题为好。
对于每一个顶点v，有两个布尔变量V_H和V_L和条件（V_H或V_L）：每对只能具有值{01，10，11}，我们可以认为的颜色1，2和3。
对于每个边（u，v）中，有要求，即（u_h，U_L）！=（V_H，V_L）。 那是，
not ((u_h and not u_l) and (v_h and not v_l) or ...)枚举所有的相等的配置和规定，即他们都不是的情况。
AND “荷兰国际集团所有这些约束条件一起给出其具有多项式大小（布尔公式O(n+m) 您可以检查，它需要多项式时间计算，以及：你在做简单的O(1)每个顶点和每条边的东西。
如果可以解决布尔公式我做，则还可以解决图着色：对于每对变量V_H和V_L，令v的颜色是一个符合这些变量的值。 通过构建公式，邻居不会有平等的颜色。
因此，如果图3的着色是NP完全，所以是布尔式-满足性。
我们知道，图的3着色是NP完全; 然而，历史上我们已经知道，通过第一表示布尔电路满足性的NP完全性，然后减少至3着色（而不是周围的其他方法）。
文章来源: What's “P=NP?”, and why is it such a famous question? [closed]
