更改

仅从定义来看，NP完全问题的存在并不直观；然而，一个简单的、人为构造的NP完全问题可以表述如下：给定一个保证在多项式时间内停止的图灵机''M''，是否存在一个''M能''接受的多项式大小的输入？<ref name="Scott" />它是NP问题，因为（给定输入）模拟''M''来验证''M''是否接受输入，这件事很简单；它是NP完全的，因为对于任何特定NP问题的验证算法都可以编码成多项式时间机器''M，''它能将解作为输入加以验证。

仅从定义来看，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问题。通过这样的转换，一大类看似不相关的问题都可以彼此简化，并且在某种意义上是“同一个问题”。

第一个被证明是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" />j这又为三分图分三角形的问题提供了一个解决方法，<ref name=":13" />然后这又能为SAT的特例3-SAT找到解决方法，<ref name=":14" />提了广义布尔可满足性的解决方案。所以数独的多项式时间解，通过一系列的机械变换，可以得到满足性的多项式时间解，进而可以用来解决多项式时间内的任何其他NP问题。通过这样的转换，一大类看似不相关的问题都可以彼此简化，并且在某种意义上是“同一个问题”。

==Harder problems==

==Harder problems==