134
个编辑
更改
跳到导航
跳到搜索
小第1行：
第1行： − 【译者】：周浩杰，如有问题欢迎交流+ − 【格式】：翻译方式是另起一个标题板块。翻译不常见人名会在后面的括号中添加英文，而常见的如夏洛克，华生，汤普森则不会。+ − + + + 第36行：
第38行： − + 第48行：
第50行： − + − 前面不太严格的表述“快速”指的是，存在以多项式时间复杂度完成任务的算法，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类算法能在多项式时间内找出答案的问题称为“P”或“P类”问题。对一些无法快速求解的问题，如果能提供答案的相关信息，那么有可能快速验证该答案。这类能在多项式时间内验证答案的问题称为NP问题，NP是"nondeterministic polynomial time"<ref group="注">非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。</ref>的缩写。+ − 这个问题被许多人认为是计算机科学中最重要的公开问题。它除了是计算理论中的一个重要问题外，它的证明也将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学和许多其他领域产生深远影响。+ − 它是克雷数学研究所选出的七个“千禧年大奖难题”之一，每一个问题，第一个正确解决的人都将奖励100万美元。+ 第66行：
第68行： − 数独游戏中有一个网格，部分格子中填写了数字，玩家需要按照特定规则在剩余网格上填写数字。给定一个任意大小的不完整数独网格，是否有至少一种符合规则的填写方式？任何一种填写方案都很容易验证，并且随着网格变大，检查答案的时间缓慢增长（多项式时间）。但是对于比较难的例子，所有已知的算法寻找可行解的时间随着网格变大，时间呈指数型增长。因此，我们认为数独是一个NP问题（快速验证）而不是P类问题（快速求解）。世界上有很多问题看起来跟数独类似，它们验证起来很快，但求解起来却很慢。研究者发现许多NP问题有一个额外的性质，即它们任意一个快速的解都能被用来求解其他任何一个NP问题，这个性质被称为NP完全性。数十年的研究也没有找到这些问题的一个快速的求解方法，所以大多数科学家怀疑这些问题不能被快速求解。但这件事还没有被证明。+
审校到example
【译者】：周浩杰，如有问题，欢迎交流与提出建议
【进度】：已完成[[wikipedia:P_versus_NP_problem|维基百科]]中除18Reference参考文献及其后面19，20，21的内容
【进度】：已完成[[wikipedia:P_versus_NP_problem|维基百科]]中除18Reference参考文献及其后面19，20，21的内容
【方式】：我一字一句翻译完后，在不更改原意的基础上修改了表达，使之更地道。比如很多很长的定语修饰一个词，我进行了拆分；合并了相同的修饰成分等。但没有对句子间的衔接进行地道化。
【引用】：see also部分加入了维基原来的超链接，其他没有。参考文献的注记有添加
【格式】：翻译方式是另起一个标题板块后翻译全部内容，而不是一小段一小段对照翻译。翻译不常见人名会在后面的括号中添加英文，而常见的如夏洛克，华生，汤普森则不会。
【引用】：see also部分加入了维基原来的超链接，其他板块没有。参考文献的注记有添加
【问题】：部分参考文献爬取下来存在格式问题，图片没爬取下来
【问题】：部分参考文献爬取下来存在格式问题，图片没爬取下来
P/NP问题的答案将决定可在多项式时间内验证的计算问题是否也可以在多项式时间内解决。当前，科学家广泛认为P ≠ NP，若它被证明，将意味着在NP类计算问题中有一些问题是难以通过算法计算的。也就是说，他们不能在多项式时间内解决，但答案可以在多项式时间内验证。简单的来说，P ≠ NP代表部分问题是“困难”的，反之，如果P = NP则意味着所有计算问题都会“容易”解决。
P/NP问题的答案将决定可在多项式时间内验证的计算问题是否也可以在多项式时间内解决。当前，科学家广泛认为P ≠ NP，若它被证明，将意味着在NP类计算问题中有一些问题是难以通过算法计算的。也就是说，他们不能在多项式时间内解决，但答案可以在多项式时间内验证。简单的来说，P ≠ NP代表部分问题是“困难”的，反之，如果P = NP则意味着所有计算问题都会“容易”解决。
The problem is considered by many to be the most important open problem in [[computer science]].<ref>{{cite journal | last1 = Fortnow | first1 = Lance | author-link = Lance Fortnow | year = 2009 | title = The status of the P versus NP problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78–86 | doi = 10.1145/1562164.1562186 | citeseerx = 10.1.1.156.767 | s2cid = 5969255 | access-date = 26 January 2010 | archive-url = https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | archive-date = 24 February 2011 | url-status = dead }}</ref> Aside from being an important problem in [[computational theory]], a proof either way would have profound implications for mathematics, [[cryptography]], algorithm research, [[artificial intelligence]], [[game theory]], multimedia processing, [[philosophy]], [[economics]] and many other fields.<ref>{{Cite book|title=The Golden Ticket: P, NP, and the Search for the Impossible|last=Fortnow|first=Lance|publisher=Princeton University Press|year=2013|isbn=9780691156491|location=Princeton, NJ}}</ref>
The problem is considered by many to be the most important open problem in [[computer science]].<ref name=":5">{{cite journal | last1 = Fortnow | first1 = Lance | author-link = Lance Fortnow | year = 2009 | title = The status of the P versus NP problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78–86 | doi = 10.1145/1562164.1562186 | citeseerx = 10.1.1.156.767 | s2cid = 5969255 | access-date = 26 January 2010 | archive-url = https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | archive-date = 24 February 2011 | url-status = dead }}</ref> Aside from being an important problem in [[computational theory]], a proof either way would have profound implications for mathematics, [[cryptography]], algorithm research, [[artificial intelligence]], [[game theory]], multimedia processing, [[philosophy]], [[economics]] and many other fields.<ref name=":6">{{Cite book|title=The Golden Ticket: P, NP, and the Search for the Impossible|last=Fortnow|first=Lance|publisher=Princeton University Press|year=2013|isbn=9780691156491|location=Princeton, NJ}}</ref>
The problem is considered by many to be the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.
The problem is considered by many to be the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.
【前言部分】
【前言部分】
P/NP问题是计算机科学领域一个尚未解决的重要问题。它指是否每一个问题都既可以快速验证它的解是否正确，同时也能快速找出它的解。
P/NP问题是计算机科学<ref name=":5" />领域中一个尚未解决的重要问题。它指是否每一个问题都既可以快速验证它的解是否正确，同时也能快速找出它的解。
前面不太严格的表述“快速”指的是，存在以多项式时间复杂度完成任务的算法，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类在多项式时间内算法能找出答案的问题称为“P”或“P类”问题。对另外一些无法快速求解的问题，如果能提供跟答案有关的信息，那么有可能快速验证该答案。这类能在多项式时间内验证答案的问题称为NP问题，NP是"nondeterministic polynomial time"<ref group="注">非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。</ref>的缩写。
对P/NP问题的回答将确定一个问题能否在多项式时间内验证和求解。如果是普遍认为的P≠NP，那么这意味着NP中有一些问题求解比验证更困难：它们不能在多项式时间内求解，但可以在多项式时间内验证。
对P/NP问题的回答将确定一个问题能否在多项式时间内验证和求解。如果是普遍认为的P≠NP，那么这意味着NP中有一些问题求解比验证更困难：它们不能在多项式时间内求解，但可以在多项式时间内验证。
这被许多人认为是计算机科学中最重要的公开问题。除了它是计算理论中的一个重要问题外，它的证明也将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学等许多其他领域产生深远影响。<ref name=":6" />
它是克雷数学研究所选出的七个“千禧年大奖难题”之一，其中每一个问题，第一个正确解决的人都将奖励100万美元。
== Example==
== Example==
==例子==
==例子==
数独游戏中有一个网格，网格中部分格子已填写了数字，玩家需要按照特定规则在剩余格子中填写数字。给定一个任意大小的不完整数独网格，是否至少有一种符合规则的填写方案？任何一种填写方案都很容易验证，并且随着网格内方格数变多，验证答案的时间只缓慢增加（多项式时间）。但是寻找填写方案时，对于比较难的例子，所有现有的算法所需时间随网格内方格数变多呈指数级增长。因此，我们认为数独是一个NP问题（快速验证）而不是P问题（快速求解）。世界上有很多问题跟数独类似，它们验证起来很快，但求解起来却很慢。研究者发现许多NP问题有一个额外的性质，即它们任何一个高效的算法都能被用来解决任何其他NP问题，这被称为NP完全性。数十年的研究也没有找到这些问题的一个快速的求解方法，所以大多数科学家怀疑这些问题不能被快速求解。不过这件事还没有被证明。
==History==
==History==