什么是“P = NP？”，为什么这么着名？
P = NP是否可能是计算机科学领域最着名的问题。 这是什么意思？ 为什么这么有趣？
哦，为了额外的功劳，请张贴陈述真相或虚假的证据。 🙂
P代表多项式时间。 NP代表非确定性多项式时间。
定义：
-
多项式时间意味着algorithm的复杂度为O（n ^ k），其中n是数据的大小（例如，要sorting的列表中的元素的数量），并且k是常数。
-
作为数据项数量的函数， 复杂性是根据所需操作的数量来衡量的。
-
作为特定任务的基本操作， 操作是有道理的。 对于sorting的基本操作是一个比较。 对于matrix乘法，基本操作是两个数字的乘法。
现在的问题是，确定性与非确定性的含义是什么？ 有一个抽象的计算模型，一个名为图灵机（TM）的虚拟计算机。 这台机器的状态数量是有限的，还有一个无限的磁带，它具有离散的单元，其中可以写入和读取一组有限的符号。 TM在任何时候都处于其状态之一，正在看磁带上的特定单元。 根据从单元格中读取的内容，它可以在该单元格中写入新的符号，将磁带向前或向后移动一个单元格，并进入不同的状态。 这被称为状态转换。 令人惊讶的是，通过仔细地构造状态和转换，你可以devise一个TM，它相当于任何可以写入的计算机程序。 这就是为什么它被用作certificate计算机能做什么和不能做什么的理论模型。
在这里有两种关注我们的TM：确定性的和非确定性的。 一个确定性的TM只有从每个符号的每个符号的一个转换，它从磁带上读取。 一个非确定性的TM可能有几个这样的转换，即它能够同时检查几种可能性。 这就像产生多个线程一样。 不同的是，一个非确定性的TM可以产生尽可能多的这样的“线程”，而在真实的计算机上，一次只能执行特定数量的线程（等于CPU的数量）。 实际上，计算机基本上是具有有限磁带的确定性TM。 另一方面，除了可能用量子计算机之外，一个非确定性的TM不能被物理地实现。
已经certificate，任何可以通过非确定性TM解决的问题都可以通过确定性TM来解决。 但是，目前还不清楚需要多less时间。 语句P = NP意味着如果一个问题在一个非确定性的TM上需要多项式时间，那么可以build立一个确定性的TM，它也将在多项式时间内解决相同的问题。 到目前为止，还没有人能够certificate它是可以做到的，但是没有人能够certificate它不能做到。
NP完全问题意味着一个NP问题X，使得NP问题Y可以通过多项式约化减less到X. 这意味着如果有人提出了一个NP完全问题的多项式时间解，那么也将给出任何NP问题的多项式时间解。 这样就certificateP = NP。 相反，如果有人要certificateP！= NP，那么我们可以确定在传统的计算机上没有办法在多项式时间内解决NP问题。
一个NP完全问题的例子是find一个真值分配的问题，这个分配会使一个包含n个variables的布尔expression式成立。
目前在实践中，任何在非确定性TM上花费多项式时间的问题只能在确定性TM或常规计算机上以指数时间完成。
例如，解决真值分配问题的唯一方法是尝试2 ^ n个可能性。
- 如果答案可以在多项式时间内计算，则P （ P olynomial time）中的是或否问题。
- 如果可以在多项式时间内validation是的答案，那么在NP （ N on-deterministic P olynomial时间）中，是或否的问题是。
直觉上，我们可以看到，如果问题出现在P中 ，那么它就是NP 。 给出P中潜在的问题答案，我们可以通过重新计算答案来validation答案。
不太明显，更难回答的是NP中的所有问题是否都在P中 。 我们可以在多项式时间内validation答案的事实是否意味着我们可以在多项式时间内计算答案？
有许多重要的问题已知是NP完全的 （基本上，如果这些问题被certificate在P中 ，那么所有的 NP问题都被certificate在P中 ）。 如果P = NP ，那么所有这些问题将被certificate有一个有效的（多项式时间）解决scheme。
大多数科学家认为P ！= NP 。 但是，对于P = NP或P ！= NP还没有证据。 如果有人提供了猜测的证据， 他们将赢得100万美元 。
为了给出最简单的答案，我可以想到：
假设我们有一个需要一定数量的input的问题，并且有各种可能的解决scheme，这些解决scheme可能或不可能解决给定input的问题。 一个益智杂志中的逻辑谜题将是一个很好的例子：input是条件（“乔治不住在蓝色或绿色的房子里”），潜在的解决scheme是一个陈述清单（“乔治住在黄色房子，生长豌豆，并拥有狗“）。 一个着名的例子是旅行推销员的问题：给出一个城市的列表，以及从任何一个城市到其他任何城市的时间，以及时间限制，一个潜在的解决scheme将是一个推销员访问他们的顺序的城市列表，如果旅行时间的总和小于时间限制，那么它就可以工作。
如果我们能够有效地检查一个潜在的解决scheme，看看它是否有效，那么这个问题就在NP中。 例如，给出推销员按顺序访问的城市列表，我们可以将城市之间的每次旅行的时间加起来，并且容易地看到是否在时间限制之内。 如果我们能够有效地find解决scheme，那么问题出在P上。
（这里有效，这里有一个精确的math意义，实际上这意味着大问题不是不合理地难以解决的，当寻找一个可能的解决scheme时，一个低效的方法是列出所有可能的解决scheme， ，而一个有效的方法将需要search一个更有限的集合。）
因此，P = NP问题可以用这种方式expression：如果能够有效地validation上述types问题的解决scheme，您是否能够有效地find解决scheme（或者certificate没有解决scheme）？ 显而易见的答案是“为什么你应该能够？”，而这正是今天的问题。 没有人能够以这种或那种方式来certificate这一点，而这又困扰了很多math家和计算机科学家。 这就是为什么任何能certificate解决scheme的人都能从Claypool基金会获得一百万美元的收益。
我们通常假设P不等于NP，没有find解决scheme的一般方法。 如果结果是P = NP，很多事情都会改变。 例如，密码学将变得不可能，并且在互联网上具有任何types的隐私或可validation性。 毕竟，我们可以有效地把encryption的文本和密钥生成原始文本，所以如果P = NP，我们可以在事先不知道的情况下有效地find密钥。 密码破解将变得微不足道。 另一方面，我们可以有效地解决一整套的计划问题和资源分配问题。
您可能听说过NP-complete。 一个NP完全问题是一个NP（当然），具有这个有趣的性质：如果它在P中，每个NP问题都是，那么P = NP。 如果你能find一种方法来有效地解决旅行推销员的问题，或从谜题的逻辑谜题，你可以有效地解决NP中的任何事情。 NP完全问题在某种程度上是最困难的NP问题。
所以，如果你能为任何NP完全问题find一个有效的通用解决scheme，或者certificate没有这样的解决方法，那么名利就是你的。
我卑微的知识简短总结：
有一些简单的计算问题（如find图中两点之间的最短path），可以很快计算（O（n ^ k），其中n是input的大小，k是一个常数的graphics，这是顶点或边的数量））。
其他问题，比如find一个跨越图中每个顶点的path，或者从公钥中获取RSA私钥更困难（O（e ^ n））。
但CS说，问题是我们不能将非确定性的图灵机“转换”为确定性的图灵机，然而，我们可以将非确定性的finine自动机（如正则expression式parsing器）转换为确定性的可以，但机器的运行时间会很长）。 也就是说，我们必须尝试一切可能的path（通常聪明的CS教授可以排除几个）。
这是互相干扰的，因为没有人对溶剂有任何的想法。 有人说这是真的，有人说这是假的，但没有共识。 另一个值得注意的事情是，对于公钥/私钥encryption（比如RSA）来说，这种欺骗是有害的。 您可以像现在生成一个RSA密钥一样轻松地将其分解。
这是一个非常鼓舞人心的问题。
我可以补充什么，为什么问题的P =？NP部分，但是关于certificate。 不仅是一个certificate值得额外的信贷，但它将解决千年问题之一 。 最近进行了一个有趣的调查， 发表的结果（PDF）对于certificate的主题是绝对值得的。
首先是一些定义：
-
一个特定的问题是在P中，如果你可以计算一个小于
n^k对于某个k，其中n是input的大小。 例如，sorting可以在小于n^2n log n完成，因此sorting是多项式时间。 -
如果存在一个
k，那么存在一个问题在NP中，使得存在至多n^k的大小的解决scheme，其可以在至多n^k时间内进行validation。 以图的三着色：给定一个图，三着色是大小为O(n)的（顶点，颜色）对的列表，并且可以在时间O(m)（或O(n^2)）所有邻居是否有不同的颜色。 所以一个图只有在有一个简短且易于validation的解决scheme时才是可着色的。
NP的等价定义是“在多项式时间内由N个不确定性图灵机可解的问题”。 虽然这告诉你名字来自哪里，但它不会给你NP NP问题的直觉。
注意P是NP的一个子集：如果你可以在多项式时间内find解，那么就有一个解决scheme可以在多项式时间内进行validation – 只要检查给定的解与你能find的解相等。
为什么问题P =? NP P =? NP有趣？ 要回答这个问题，首先需要看看NP完全问题是什么。 简单地说，
- 如果（1）L在P中，且（2）求解L的algorithm可用于解决NP中的任何问题L'，则问题L是NP-完全的; 也就是说，给定一个L'的实例，当且仅当L'的实例有一个解决scheme时，才可以创build一个具有解决scheme的L的实例。 从forms上讲，NP中的每个问题L'都可以归结为L
注意，L的实例必须是多项式时间可计算的，并且具有L'大小的多项式大小; 这样，在多项式时间内求解NP完全问题给了我们所有 NP问题的多项式时间解。
下面是一个例子：假设我们知道图的3染色是NP难题。 我们想certificate决定布尔公式的可满足性也是NP难题。
对于每个顶点v，有两个布尔variablesv_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 ...)列举所有的平等configuration，并规定他们都不是这种情况。
AND将所有这些约束条件一起给出具有多项式大小（ O(n+m) ）的布尔公式。 您可以检查是否需要计算多项式时间：您正在为每个顶点和每个边执行简单的O(1)填充。
如果你能解决我所做的布尔公式，那么你也可以解决图着色问题：对于每一对variablesv_h和v_l，让v的颜色与那些variables的值匹配。 通过构build公式，邻居不会有相同的颜色。
因此，如果图的3染色是NP完全的，布尔公式可满足性也是。
我们知道图的3染色是NP完全的; 然而，历史上我们已经知道，首先显示布尔电路可满足性的NP完全性，然后将其降低到3色可用性（而不是其他方式）。
