134
个编辑
更改
跳到导航
跳到搜索
小第109行：
第109行： − + 第129行：
第129行： − + − 第一个被证明是NP完全的问题是布林满足性问题，也被称为SAT。这也就是库克-里文定理，即，只要SAT问题可以通过确定性图灵机在多项式时间内解决，那么所有NP问题都可以在多项式时间内解决。不过，在这个问题被证明为NP完全之后，又有很多其他问题也被简单的归约证明为NP完全的，如前面讨论过的数独。具体来说，证明数独在多项式时间内的解也可以拓展用在拉丁方阵问题上。再进一步，三分图分割问题的解决为SAT的特殊情形3-SAT问题找到了一个解。因此，通过数独的多项式时间解的一系列变换，得出了SAT的一个多项式时间解，而这个多项式时间解又可用于在多项式时间内解决任何其他NP问题。所以说，一大类看似不相关的问题都可以转换后归化为彼此，在某种意义上就是“同一个问题”。+ − + − + − NP难问题是那些至少和NP问题一样难；i、 例如，所有NP问题都可以（在多项式时间内）归约为它们。NP难问题不一定属于NP；i、 例如，它们不需要在多项式时间内有可验证的解。+ − + − 仅从定义来看，NP完全问题的存在并不明显；然而，一个简单的、人为的NP完全问题可以表述如下：给定一个保证在多项式时间内停止的图灵机M的描述，是否存在一个M将接受的多项式大小的输入？[11] 它在NP中是因为（给定一个输入）通过模拟M来检查M是否接受输入很简单；它是NP完全的，因为NP中问题的任何特定实例的验证器都可以被编码为多项式时间机器M，该机器将待验证的解作为输入。然后，实例是否为yes或no的问题取决于是否存在有效的输入。+ − 第一个被证明是NP完全的自然问题是布尔可满足性问题，也称为SAT。如上所述，这是库克-莱文定理；它的可满足性是NP完全的证明包含了图灵机器的技术细节，因为它们与NP的定义有关。然而，在这个问题被证明是NP完全的之后，通过约化证明提供了一种更简单的方法来证明许多其他问题也是NP完全的，包括前面讨论的数独游戏。在这种情况下，证明表明多项式时间的数独解也可以用来在多项式时间内完成拉丁方。[12] 这反过来为将三部图划分为三角形的问题提供了一个解决方案，[13]然后可以用来为SAT的特例3-SAT找到解决方案，[14]然后提供了一般布尔可满足性的解决方案。所以数独的多项式时间解，通过一系列的机械变换，可以得到满足性的多项式时间解，进而可以用来解决多项式时间内的任何其他NP问题。通过这样的转换，一大类看似不相关的问题都可以彼此简化，并且在某种意义上是“同一个问题”。+
→NP完全性： 输入i打不了字，先保存一下
在这种分析中，需要用于分析时间的计算机模型。通常，此类模型假定计算机具有确定性（给定计算机的当前状态，对于任何输入，只采取一种可能的操作）和连续性（它一个接一个地执行操作）。
在这种分析中，需要用于分析时间的计算机模型。通常，此类模型假定计算机具有确定性（给定计算机的当前状态，对于任何输入，只采取一种可能的操作）和连续性（它一个接一个地执行操作）。
在这个理论中，P类问题由所有这样的决策问题组成，它们可以在确定有限性的机器上求解，运行时间是输入规模的多项式函数；NP类由所有这样的决策问题组成，如果有正确的信息，它们的定解可以在多项式时间内验证，或者说，它的解可以用非确定图灵机在多项式时间内找到。<ref name=":11" />很明显，P⊆ NP。可以说，理论计算机科学中最重大的公开问题就是这两类问题间的关系：<blockquote>P是否等于NP？</blockquote>自2002年以来，威廉·加萨奇（William Gasarch）就这一问题及相关问题对研究人员进行了三次民意调查。<ref name="poll" /><ref name="poll2" /><ref name="poll3" />认为P ≠ NP的人数一直在增加。2019年，88%的人相信P ≠ NP，而2012年和2002年分别为83%和61%。当受访者仅限于专家时，2019年这个比例是99%。<ref name="poll3" />这些调查结果无法说明P = NP正确与否。正如加萨其（Gasarch）自己所说：“这并没有让我们离解决P =？NP更进一步或是知道它什么时候会被解决，但它试图成为对这个时代主观观点的客观报道。”
在这个理论中，P类问题由所有这样的决策问题组成，它们可以在确定有限性的机器上求解，运行时间是输入规模的多项式函数；NP类由所有这样的决策问题组成，如果有正确的信息，它们的定解可以在多项式时间内验证，或者说，它的解可以用非确定图灵机在多项式时间内找到。<ref name=":11" />很明显，P⊆ NP。可以说，理论计算机科学中最重大的公开问题就是这两类问题间的关系：<blockquote>P是否等于NP？</blockquote>自2002年以来，威廉·加萨奇（William Gasarch）就这一问题及相关问题对研究人员进行了三次民意调查。<ref name="poll" /><ref name="poll2" /><ref name="poll3" />认为P ≠ NP的人数一直在增加。2019年，88%的人相信P ≠ NP，而2012年和2002年分别为83%和61%。当受访者仅限于专家时，2019年这个比例是99%。<ref name="poll3" />这些调查结果无法说明P = NP正确与否。正如加萨其（Gasarch）自己所说：“这并没有让我们离解决P =？NP更进一步或是知道其什么时候会被解决，但它试图成为对这个时代主观观点的客观报道。”
==NP-completeness==
==NP-completeness==
<small>其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。</small>
<small>其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。</small>
The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref>{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref>{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref>{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713–717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability. So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".
The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref name=":12">{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref name=":13">{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref name=":14">{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713–717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability. So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".
The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, proof by reduction provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete Latin squares in polynomial time. This in turn gives a solution to the problem of partitioning tri-partite graphs into triangles, which could then be used to find solutions for the special case of SAT known as 3-SAT, which then provides a solution for general Boolean satisfiability. So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".
The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, proof by reduction provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete Latin squares in polynomial time. This in turn gives a solution to the problem of partitioning tri-partite graphs into triangles, which could then be used to find solutions for the special case of SAT known as 3-SAT, which then provides a solution for general Boolean satisfiability. So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".
第一个被证明是NP完全的问题是布尔满足性问题，也被称为SAT。这也就是库克-里文定理，即，只要SAT问题可以通过确定性图灵机在多项式时间内解决，那么所有NP问题都可以在多项式时间内解决。不过，在这个问题被证明为NP完全之后，又有很多其他问题也被简单的归约证明为NP完全的，如前面讨论过的数独。具体来说，证明数独在多项式时间内的解也可以拓展用在拉丁方阵问题上。再进一步，三分图分割问题的解决为SAT的特殊情形3-SAT问题找到了一个解。因此，通过数独的多项式时间解的一系列变换，得出了SAT的一个多项式时间解，而这个多项式时间解又可用于在多项式时间内解决任何其他NP问题。所以说，一大类看似不相关的问题都可以转换后归化为彼此，在某种意义上就是“同一个问题”。
==NP完全问题==
==NP完全性==
对于解决P=NP问题，NP完全性这个概念非常有用。NP完全问题是一组其他任何NP问题都可以在多项式时间内归约，并且其解仍然可以在多项式时间内得到验证问题。也就是说，任何NP问题都可以转化为任何NP完全问题。不严格的讲，NP完全问题是一个至少和NP中其他任何问题一样“难”的NP问题。
对于解决P = NP问题，NP完全性这个概念非常有用。NP完全问题是这样一组问题，其他任何NP问题都可以在多项式时间内归约成它，并且它的解仍然可以在多项式时间内得到验证。也就是说，任何NP问题都可以转化为任何NP完全问题。不严格的说，NP完全问题是一个至少和NP中最难的问题一样“难”的NP问题。
NP难问题是那些至少和NP问题一样难；也就是说所有NP问题都可以（在多项式时间内）归约成它们。NP难问题不一定是NP问题；也就是说它们的解不一定能在多项式时间内验证。
例如，根据库克-莱文定理，布尔可满足性问题是NP完全问题，因此NP中任何问题都可以在多项式时间内被机器转化为布尔可满足性问题。布尔可满足性问题是许多此类NP完全问题之一。如果任何NP完全问题在P中，那么P=NP。然而，许多重要的问题已经被证明是NP完全的，并且没有任何一个问题有高效的算法。
例如，根据库克-莱文定理，布尔可满足性问题是NP完全问题，因此NP中任何问题都可以在多项式时间内转化为布尔可满足性问题。布尔可满足性问题是许多此类NP完全问题之一。如果任何NP完全问题属于P问题，那么P = NP。然而，许多重要的问题已经被证明是NP完全的，并且它们中的任何一个问题都没有高效的算法。
仅从定义来看，NP完全问题的存在并不直观；然而，一个简单的、人为构造的NP完全问题可以表述如下：给定一个保证在多项式时间内停止的图灵机''M''，是否存在一个''M能''接受的多项式大小的输入？<ref name="Scott" />它是NP问题，因为（给定输入）模拟''M''来验证''M''是否接受输入，这件事很简单；它是NP完全的，因为对于任何特定NP问题的验证算法都可以编码成多项式时间机器''M，''它能将解作为输入加以验证。
第一个被证明是NP完全的非人造问题是布尔可满足性问题，也称为SAT。如上所述，这是库克-莱文定理；<u>它的可满足性证明是NP完全的，包含了图灵机的技术细节，同时跟NP的定义有关。</u>【划线的这句话，原文没看懂意思。在这节的第五段 [[wikipedia:P_versus_NP_problem#NP-completeness|its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP.]]】然而，在它被证明是NP完全问题之后，通过归约可以找到一种更简单的方法来证明许多其他问题也是NP完全的，包括前面讨论的数独游戏。在这个例子中，在多项式时间内求出数独解的证明过程也可以用来在多项式时间内解决拉丁方阵问题。<ref name=":12" />这又为三分图分三角形的问题提供了一个解决方法，<ref name=":13" />然后这又能为SAT的特例3-SAT找到解决方法，<ref name=":14" />提了广义布尔可满足性的解决方案。所以数独的多项式时间解，通过一系列的机械变换，可以得到满足性的多项式时间解，进而可以用来解决多项式时间内的任何其他NP问题。通过这样的转换，一大类看似不相关的问题都可以彼此简化，并且在某种意义上是“同一个问题”。
==Harder problems==
==Harder problems==