更改

【前言部分】

【前言部分】

P/NP问题是计算机科学<ref name=":5" />领域中一个尚未解决的重要问题。它指是否每一个问题都既可以快速验证它的解是否正确，同时也能快速找出它的解。

P/NP问题是计算机科学领域中一个尚未解决的重要问题。它指是否每一个问题都既可以快速验证它的解是否正确，同时也能快速找出它的解。

前面不太严格的表述“快速”指的是，存在以多项式时间复杂度完成任务的算法，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类在多项式时间内算法能找出答案的问题称为“P”或“P类”问题。对另外一些无法快速求解的问题，如果能提供跟答案有关的信息，那么有可能快速验证该答案。这类能在多项式时间内验证答案的问题称为NP问题，NP是"nondeterministic polynomial time"<ref group="注">非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。</ref>的缩写。

前面不太严格的表述“快速”指的是，存在以多项式时间复杂度完成任务的算法，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类在多项式时间内算法能找出答案的问题称为“P”或“P类”问题。对另外一些无法快速求解的问题，如果能提供跟答案有关的信息，那么有可能快速验证该答案。这类能在多项式时间内验证答案的问题称为NP问题，NP是"nondeterministic polynomial time"<ref group="注">非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。</ref>的缩写。

对P/NP问题的回答将确定一个问题能否在多项式时间内验证和求解。如果是普遍认为的P≠NP，那么这意味着NP中有一些问题求解比验证更困难：它们不能在多项式时间内求解，但可以在多项式时间内验证。

对P/NP问题的回答将确定一个问题能否在多项式时间内验证和求解。如果是普遍认为的P≠NP，那么这意味着NP中有一些问题求解比验证更困难：它们不能在多项式时间内求解，但可以在多项式时间内验证。

这被许多人认为是计算机科学中最重要的公开问题。除了它是计算理论中的一个重要问题外，它的证明也将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学等许多其他领域产生深远影响。<ref name=":6" />

这被许多人认为是计算机科学中最重要的公开问题。<ref name=":5" />除了它是计算理论中的一个重要问题外，它的证明也将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学等许多其他领域产生深远影响。<ref name=":6" />

它是克雷数学研究所选出的七个“千禧年大奖难题”之一，其中每一个问题，第一个正确解决的人都将奖励100万美元。

它是克雷数学研究所选出的七个“千禧年大奖难题”之一，其中每一个问题，第一个正确解决的人都将奖励100万美元。

==历史==

==历史==

1971年，史蒂芬·库克（Stephen Cook）在他的开创性论文《定理证明过程的复杂性》<ref name=":7" />（"The complexity of theorem proving procedures"）中精确表述了P/NP问题。在1973年雷纳德·里文（Leonid Levin）也独立提出该问题<ref name=":8" />。

1971年，史蒂芬·库克（Stephen Cook）在他的开创性论文《定理证明过程的复杂性》<ref name=":7" />（"The complexity of theorem proving procedures"）中精确表述了P/NP问题。在1973年雷纳德·里文（Leonid Levin）也独立提出该问题。<ref name=":8" />

虽然P/NP问题在1971年才被正式定义，但是之前已经有人在考虑这个问题，内容包括证明的难度和潜在的影响。1955年，数学家约翰·纳什（John Nash）给美国国家安全局（NSA）写了一封信，他推测破解一个十分复杂的密码所需要的时间随密钥长度指数级增长。<ref name=":9" />如果能证明这一点（纳什有点怀疑），这意味着P ≠ NP，因为任何一个密钥都可以轻易在多项式时间得到验证。1956年，库尔特·哥德尔（ Kurt Gödel）在写给约翰·冯·诺伊曼（ John von Neumann）的信中提到了这个潜在问题。哥德尔（Gödel）想要知道定理证明（现在被认为是co-NP完全问题）是否可以在二次项或线性时间内得到结果，<ref name=":10" />如果是的话，其最重要的影响之一是寻找数学定理的证明过程将可以自动化。

虽然P/NP问题在1971年才被正式定义，但是之前已经有人在考虑这个问题，内容包括证明的难度和潜在的影响。1955年，数学家约翰·纳什（John Nash）给美国国家安全局（NSA）写了一封信，他推测破解一个十分复杂的密码所需要的时间随密钥长度指数级增长。<ref name=":9" />如果能证明这一点（纳什有点怀疑），这意味着P ≠ NP，因为任何一个密钥都可以轻易在多项式时间得到验证。1956年，库尔特·哥德尔（ Kurt Gödel）在写给约翰·冯·诺伊曼（ John von Neumann）的信中提到了这个潜在问题。哥德尔（Gödel）想要知道定理证明（现在被认为是co-NP完全问题）是否可以在二次项或线性时间内得到结果，<ref name=":10" />如果是的话，其最重要的影响之一是寻找数学定理的证明过程将可以自动化。