P/NP问题

【译者】：周浩杰，如有问题，欢迎交流与提出建议

【进度】：已完成维基百科中除18Reference参考文献及其后面19，20，21的内容

【方式】：我一字一句翻译完后，在不更改原意的基础上修改了表达，使之更地道。比如很多很长的定语修饰一个词，我进行了拆分；合并了相同的修饰成分等。但没有对句子间的衔接进行地道化。

【格式】：翻译方式是另起一个标题板块后翻译全部内容，而不是一小段一小段对照翻译。翻译不常见人名会在后面的括号中添加英文，而常见的如夏洛克，华生，汤普森则不会。

【引用】：see also部分加入了维基原来的超链接，其他板块没有。参考文献的注记有添加

【问题】：部分参考文献爬取下来存在格式问题，图片没爬取下来；在引用后拼写含有i字母会有bug

【备注】：此文过于专业，虽然作为一个计科专业的本科生，我对一些概念略有涉猎，但还是有很多概念没有学过，大致通过搜索引擎学习了一下，但用一个月翻译这篇文章对于我而言时间有限，一些内容我还是没有看懂，所以我就望文生义，这些内容我都在旁边做了说明。

此词条暂由彩云小译翻译，翻译字数共6121，未经人工整理和审校，带来阅读不便，请见谅。

模板:Pp-move-indef 模板:Unsolved 模板:Millennium Problems

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

P/NP问题是众多尚未解决的计算机理论和算法复杂度中最重要的一个难题，分别由加拿大科学家史蒂芬·库克和俄罗斯科学家雷纳德·里文在1970年代独立提出。它也被克雷数学研究所列为“七大千禧大奖难题”之一，第一个解决的人将100万美元奖励。

The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time".^{[Note 1]}

The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time".A nondeterministic Turing machine can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.

P/NP问题的核心在于判断一个计算问题能否被快速的解决和答案可被快速的验证。前面的“快速”指是否存在一个只用多项式时间内解决计算问题的算法，也就是说算法完成计算任务的时间与任务的输入量呈多项式函数相关，而不是线形时间或指数时间。复杂度P类是指一类可以通过多项式时间内的算法解决的计算问题。还有一类计算问题，它们没有已知的可以在多项式时间内解决的算法，但可以在多项式时间内快速验证答案是可能的，这类计算问题即复杂度NP类问题。如果从以图灵机来理解，一个非确定型图灵机因其不受以往确定状态的影响，可以在多项式时间内随机移动到NP类问题的答案态，再通过传统方式验证它。那么这种机器只可以用作理论模型，但没有用它解决实际问题的价值。

An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turns out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

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.^[1] 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.^[2]

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问题是计算机科学中最重要的问题，而且这个问题的证明都将对数学、密码学、算法研究、人工智能、博弈论、多媒体处理、哲学、经济学和许多其他领域产生深远的影响。

It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.

【前言部分】

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

前面不太严格的表述“快速”指的是，存在以多项式时间复杂度完成任务的算法，也就是说完成任务的时间是关于算法输入规模的多项式函数（与指数时间相对）。这类在多项式时间内算法能找出答案的问题称为“P”或“P类”问题。对另外一些无法快速求解的问题，如果能提供跟答案有关的信息，那么有可能快速验证该答案。这类能在多项式时间内验证答案的问题称为NP问题，NP是"nondeterministic polynomial time"^{[注 1]}的缩写。

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

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

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

Example

Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger. So, Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable). Thousands of other problems seem similar, in that they are fast to check but slow to solve. Researchers have shown that many of the problems in NP have the extra property that a fast solution to any one of them could be used to build a quick solution to any other problem in NP, a property called NP-completeness. Decades of searching have not yielded a fast solution to any of these problems, so most scientists suspect that none of these problems can be solved quickly. This, however, has never been proven.

我们在此以数独为例以理解以上的概念。在数独当中，玩家会获得一个部分填充的数字网格，玩家按照一定的规则完成网格中剩余的数字则算胜利。问题是，已知一个任意大小的数字网格，我们如何知道网格至少有一个满足规则的填写答案？在此，如果我们给定任意的填写答案都很容易验证，且随着网格的增大，检查答案的呈多项式时间增长。但是反过来，如果我们想要通过算法寻找解决答案，随网格变大，却需要指数性时间的增长。因此，我们认为数独是一个典型的NP问题，即答案可快速验证，但不太能快速解决。世界上有很多问题看起来跟数独很相似，它们检查起来很快，但解决起来却很慢。不过，科学家发现，NP类问题中的许多计算问题都有一个特性，即任何一个问题的快速解都可以帮助解决NP类中的任何其他问题，这个特性称为NP完全性（英文：NP- Completeness）。由于我们暂未找到这些NP完全性问题的快速解，所以大多数科学家怀疑这类问题不可能找到快速解。

例子

数独游戏中有一个网格，网格中部分格子已填写了数字，玩家需要按照特定规则在剩余格子中填写数字。给定一个任意大小的不完整数独网格，是否至少有一种符合规则的填写方案？任何一种填写方案都很容易验证，并且随着网格内方格数变多，验证答案的时间只缓慢增加（多项式时间）。但是寻找填写方案时，对于比较难的例子，所有现有的算法所需时间随网格内方格数变多呈指数级增长。因此，我们认为数独是一个NP问题（快速验证）而不是P问题（快速求解）。世界上有很多问题跟数独类似，它们验证起来很快，但求解起来却很慢。研究者发现许多NP问题有一个额外的性质，即它们任何一个高效的算法都能被用来解决任何其他NP问题，这被称为NP完全性。数十年的研究也没有找到这些问题的一个快速的求解方法，所以大多数科学家怀疑这些问题不能被快速求解。不过这件事还没有被证明。

History

The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures"^[3] (and independently by Leonid Levin in 1973^[4]).

The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" (and independently by Leonid Levin in 1973).

1971年，多伦多大学教授史蒂芬·库克在他的开创性论文《定理证明过程的复杂性》（英文："The complexity of theorem proving procedures"）中提出了P/NP问题的精确陈述，这个问题后来又在1973年由波士顿大学教授雷纳德·里文独立提出。

Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician John Nash wrote a letter to the NSA, where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key.^[5] If proved (and Nash was suitably skeptical) this would imply what is now called P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann. Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time,^[6] and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.

Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician John Nash wrote a letter to the NSA, where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key. If proved (and Nash was suitably skeptical) this would imply what is now called P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann. Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time, and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.

虽然P/NP问题在1971年才被正式定义，但是之前已经有人了想到了这个问题、证明的难度和潜在的后果。1955年，数学家约翰·纳什给美国国家安全局写了一封信，他推测破解一个足够复杂的密码需要密钥长度呈指数增长。如果有人能证明这一点，那么这就意味着P ≠ NP，因为任意一个密钥都可以在多项式时间内得到验证。1956年，库尔特·哥德尔在写给约翰·冯·诺伊曼的信中提到了这个潜在的问题。哥德尔想要知道自动定理证明问题（现在被认为是co-NP完全问题）是否可以在二次或线性时间内解决，并指出了最重要的后果之一——如果可以的话，数学定理证明过程将可以自动化。

历史

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

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

Context

== The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).

= = 提出背景 = = 探讨P/NP类问题是被放在计算复杂性理论大背景中进行的，尤其是有关计算过程资源消耗的问题。这类资源消耗问题主要讨论计算时间（解决问题需要多少步骤）和计算空间（解决问题需要多少内存）。

In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer's present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other). In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer's present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other).

在这类问题的分析中，我们需要设计一个计算时间利用的模型。一般来说，这类模型建立在计算机确定态的和顺序态基础之上，也就是说，给定计算机的当前状态和任何输入，计算机只可能执行一种行为，并且只能按顺序地执行任务。

In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.^[7] Clearly, P ⊆ NP. Arguably, the biggest open question in theoretical computer science concerns the relationship between those two classes:

Is P equal to NP? In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20. Clearly, P ⊆ NP. Arguably, the biggest open question in theoretical computer science concerns the relationship between those two classes:

Is P equal to NP?

P类问题指一类由%确定的按顺序的%的计算机完成并能在多项式时间内解决的问题；NP问题指一类可以在多项式时间内验证答案的问题，或者通过%非确定性的%计算机上可以在多项式时间内找到答案的问题。（来源：迈克尔 · 西普塞尔: 美国计算理论学会简介，第二版，国际版，第270页。汤姆森课程科技，2006。定义7.19和定理7.20。）可见，P ⊆ NP。所以说，理论计算科学中最大的开放性问题就是这两个问题类之间的关系: P类问题等价于NP类问题吗？

Since 2002, William Gasarch has conducted three polls of researchers concerning this and related questions.^[8]^[9]^[10]Confidence that P ≠ NP has been increasing – in 2019, 88% believed P ≠ NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believe P ≠ NP.^[10] These polls do not imply anything about whether P=NP is true, as stated by Gasarch himself: ″This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era.″ Since 2002, William Gasarch has conducted three polls of researchers concerning this and related questions. Confidence that P ≠ NP has been increasing – in 2019, 88% believed P ≠ NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believe P ≠ NP. These polls do not imply anything about whether P=NP is true, as stated by Gasarch himself: ″This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era.″

2002年以来，威廉·加萨奇就这一问题对研究人员进行了三次调查。相信P类不等于NP类的人数一直在增加——2019年，88%的人相信P类不等于NP类，而2012年和2002年的这一比例分别为83% 和61%。如果只关注专家的态度，2019年的结果显示99%的人相信P类不等于NP类。这些调查并非代表P = NP，如加萨奇说：“这个调查的目的不是为了更接近真相，而是为了更客观的了解学者们对一个未知真相的主观意见。” ==

背景

复杂性类中P和NP的关系是在计算复杂性理论中被研究的，计算复杂性理论是计算理论的分支，处理计算任务所需资源的相关问题。最常见的资源是时间（求解问题需要多少步骤）和空间（求解问题需要多少内存）。

在这种分析中，需要用于分析时间的计算机模型。通常，此类模型假定计算机具有确定性（给定计算机的当前状态，对于任何输入，只采取一种可能的操作）和连续性（它一个接一个地执行操作）。

在这个理论中，P类问题由所有这样的决策问题组成，它们可以在确定有限性的机器上求解，运行时间是输入规模的多项式函数；NP类由所有这样的决策问题组成，如果有正确的信息，它们的定解可以在多项式时间内验证，或者说，它的解可以用非确定图灵机在多项式时间内找到。^[7]很明显，P⊆ NP。可以说，理论计算机科学中最重大的公开问题就是这两类问题间的关系：

P是否等于NP？

自2002年以来，威廉·加萨奇（William Gasarch）就这一问题及相关问题对研究人员进行了三次民意调查。^[8]^[9]^[10]认为P ≠ NP的人数一直在增加。2019年，88%的人相信P ≠ NP，而2012年和2002年分别为83%和61%。当受访者仅限于专家时，2019年这个比例是99%。^[10]这些调查结果无法说明P = NP正确与否。正如加萨其（Gasarch）自己所说：“这并没有让我们离解决P =？NP更进一步或是知道其什么时候会被解决，但它试图成为对这个时代主观观点的客观报道。”

NP-completeness

模板:Main article To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP. To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.

为了解决P/NP问题，了解NP完全性的概念是非常有帮助的。NP完全问题指一类可以将NP问题简化为多项式时间内可解的问题，而且这类问题的解也可以在多项式时间内验证。理论上讲，任何NP问题都可以转化为NP完全问题。换一种方式来说，一个NP完全问题至少跟其他NP问题一样“困难”。

NP-hard problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time. NP-hard problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time.

NP困难问题是指至少和NP问题一样困难的问题，也就是说，所有NP问题都可以（在多项式时间内）简化为NP困难问题。NP困难问题不一定是NP问题，它们不需要在多项式时间内有可验证的解。

For instance, the Boolean satisfiability problem is NP-complete by the Cook–Levin theorem, so any instance of anyproblem in NP can be transformed mechanically into an instance of the Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems have been shown to be NP-complete, and no fast algorithm for any of them is known. For instance, the Boolean satisfiability problem is NP-complete by the Cook–Levin theorem, so any instance of any problem in NP can be transformed mechanically into an instance of the Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems have been shown to be NP-complete, and no fast algorithm for any of them is known.

例如，根据 Cook-Levin 定理，%布尔可满足性问题%是NP完全问题，因此任何 NP 问题的实例都可以在多项式时间内被转化为%布尔可满足性问题%的实例。它是许多NP完全问题中的一个。如果任意一个NP完全问题在P类问题中，那么P = NP。然而，许多重要的问题已经被证明是NP完全的，并且至今没有一个更快速的算法。

Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept?^[11] It is in NP because (given an input) it is simple to check whether M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists. Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept? It is in NP because (given an input) it is simple to check whether M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.

其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。

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.^[12] This in turn gives a solution to the problem of partitioning tri-partite graphs into triangles,^[13] which could then be used to find solutions for the special case of SAT known as 3-SAT,^[14] 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完全性

对于解决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完全问题可以表述如下：给定一个保证在多项式时间内停止的图灵机M，是否存在一个M能接受的多项式大小的输入？^[11]它是NP问题，因为（给定输入）模拟M来验证M是否接受输入，这件事很简单；它是NP完全的，因为对于任何特定NP问题的验证算法都可以编码成多项式时间机器M，它能将解作为输入加以验证。

第一个被证明是NP完全的非人造问题是布尔可满足性问题，也称为SAT。如上所述，这是库克-莱文定理；它的可满足性证明是NP完全的，包含了图灵机的技术细节，同时跟NP的定义有关。【划线的这句话，原文没看懂意思。在这节的第五段 its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP.】然而，在它被证明是NP完全问题之后，通过归约可以找到一种更简单的方法来证明许多其他问题也是NP完全的，包括前面讨论的数独游戏。在这个例子中，在多项式时间内求出数独解的证明过程同样也可以用来在多项式时间内解决拉丁方阵问题。^[12]接着这为三分图划分三角形的问题提供了一个解决方法，^[13]然后这又能为SAT的特例3-SAT找到解决方法，^[14]之后这又能用来解决广义布尔可满足性问题。所以数独的多项式时间解，通过一系列的形式变换，能够得到可满足性问题的多项式时间解，进而这又可以用来在多项式时间内解决任何其他NP问题。通过这样的转换，许多看似不相关的问题都可以彼此归约，或者在某种意义上是“同一个问题”。

Harder problems

Although it is unknown whether P = NP, problems outside of P are known. Just as the class P is defined in terms of polynomial running time, the class EXPTIME is the set of all decision problems that have exponential running time. In other words, any problem in EXPTIME is solvable by a deterministic Turing machine in O(2^p(n)) time, where p(n) is a polynomial function of n. A decision problem is EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to it. A number of problems are known to be EXPTIME-complete. Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the time hierarchy theorem, they cannot be solved in significantly less than exponential time. Examples include finding a perfect strategy for chess positions on an N × N board^[15] and similar problems for other board games.^[16]

Although it is unknown whether P = NP, problems outside of P are known. Just as the class P is defined in terms of polynomial running time, the class EXPTIME is the set of all decision problems that have exponential running time. In other words, any problem in EXPTIME is solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. A decision problem is EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to it. A number of problems are known to be EXPTIME-complete. Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the time hierarchy theorem, they cannot be solved in significantly less than exponential time. Examples include finding a perfect strategy for chess positions on an N × N board and similar problems for other board games.

虽然P=NP是否存在尚不清楚，但P类以外的问题是已知的。正如P类是根据多项式时间定义的一样，EXPTIME类判定性问题是所有具有指数时间的问题集合。也就是说，EXPTIME中的任何判定性问题都可以通过确定性图灵机在O(2^p(n))时间内中解决，其中p(n)是n的多项式函数。如果一个判定性问题是在EXPTIME的，那么它就是EXPTIME完全的，而且EXPTIME中的每个问题都有一个多项式时间内的多对一归约。因为我们可以证明P≠EXPTIME，所以所有这些问题都在P类之外，且由时间阶层定理可知，它们的解决不可能远远少于EXPTIME。例如，国际象棋或者其他棋盘游戏中，在已知在N×N棋盘上找到完美的解法就属于EXPTIME类问题。

The problem of deciding the truth of a statement in Presburger arithmetic requires even more time. Fischer and Rabin proved in 1974^[17] that every algorithm that decides the truth of Presburger statements of length n has a runtime of at least [math]\displaystyle{ 2^{2^{cn}} }[/math] for some constant c. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

The problem of deciding the truth of a statement in Presburger arithmetic requires even more time. Fischer and Rabin proved in 1974 that every algorithm that decides the truth of Presburger statements of length n has a runtime of at least 2^{2^{cn}} for some constant c. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

除EXPTIME之外，科学家还发现了所需时间更长的问题。比较标志性的问题是在皮尔斯伯格算术（Presburger arithmetic）中判定任意陈述的正确性的问题。美国计算机学家迈克尔·菲舍尔和以色列数学家迈尔克·罗宾在1974年证明，已知一个皮尔斯伯格语句长度n，判断语句正确性所需的时间至少为2^{2^{cn}，c为常数，该时间比指数时间更长。比这类问题更困难的是不可判定问题，比如停机问题。任何算法都不能完全解决这些问题，因为对于任何特定的算法来说，至少有一个输入的算法不会产生正确的答案；它要么会产生错误的答案，在没有给出结论性答案的情况下结束，要么永远运行下去而不产生任何答案。

It is also possible to consider questions other than decision problems. One such class, consisting of counting problems, is called #P: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?" Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems.^[18] For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many. Many of these problems are #P-complete, and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.

It is also possible to consider questions other than decision problems. One such class, consisting of counting problems, is called #P: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?" Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems. For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many. Many of these problems are #P-complete, and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.

判定性问题以外的其他问题也曾被广泛研究，例如#P类，这类问题由计数问题组成。NP类问题讨论的是是否有解，而#P类问题讨论的是有多少个解。很明显，#P类问题至少和相应的NP类问题一样困难，因为如果计数大于零，解的计数会立即告诉你是否至少有一个解存在。但反直觉的是一些#P类问题反而与简单的P类问题范围相交，即很容易判断是否存在解决方案，但很难判断有多少解决方案。这些问题中有许多是#P完全的，也是#P类中最难的问题之一，其中任何一个问题的多项式时间解都将转化为其他所有#P类问题的多项式时间解。

更难的问题

虽然不知道P = NP是否成立，但P类之外的问题是已知的。正如P类问题是用多项式运行时间定义的，EXPTIME类问题是所有具有指数运行时间决策问题的集合。换句话说，EXPTIME中的任何问题都可以利用确定性图灵机在O(2^p(n))时间内解决，其中p(n)是n的多项式函数。如果某个决策问题在EXPTIME类中，并且EXPTIME中的每个问题都可以通过多项式时间一次性归约（many-one reduction）得到该问题，那么这个问题是EXPTIME完全的。许多问题都是EXPTIME完全的。因此可以说明P ≠ EXPTIME，这些问题不属于P类，并且所需时间远超多项式时间。【原文的because前后，我并没理解这个逻辑关系。在该节第一段Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. 】实际上，根据时间层次定理，它们不能在显著少于指数时间的情况下求解。例如，在N×N的国际象棋棋盘上找到一个下棋的完美策略，^[15]或是其他类似的棋类游戏。^[16]

在普雷斯伯格算术中判断语句是否为真需要更多的时间。费舍尔（Fischer）和拉宾（Rabin）在1974年证明，^[17]任何算法判定一条长度为n的普雷斯伯格语句为真的运行时间至少是[math]\displaystyle{ 2^{2^{cn}} }[/math]，c是某常数。因此，该问题运行时间远超指数级。更困难的是不可判定问题，例如停机问题。任何算法都无法完全解决这些问题，因为对于任何特定的算法，至少有一个输入，该算法无法给出正确答案；它要么给出错误答案，要么在没有给出正确答案前就结束了，或是永远运行，根本没有给出任何答案。

除了判定问题之外也有值得考虑的问题。其中一类是计数问题，称为#P：与NP问题会问“有什么解决方法吗？”不同，对应的#P问题会问“有多少种解决方法？”显然，一个#P问题至少和对应的NP问题一样难，因为如果问题的解的个数大于零，这个计数值就告诉我们是否至少存在一个解。令人惊讶的是，一些被认为是困难的#P问题，其对应的P问题（例如线性时间）是简单的。^[18]对于这些问题，很容易判断是否存在解决方法，但很难判断有多少种解决方法。这些问题中有许多是#P完全的，对其中任何一个问题的多项式时间解都将使所有其他#P问题有多项式时间解，因此这是#P中最难的问题。

Problems in NP not known to be in P or NP-complete

模板:Main article In 1975, Richard E. Ladner showed that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete.^[19]Such problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.

In 1975, Richard E. Ladner showed that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. Such problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.

1975年，华盛顿大学教授理查德·兰德指出，如果P≠NP，那么在NP类中就存在既不在P类中也不在NP完全类中的问题。这类问题称为NP中间类问题。$图同构问题、离散对数问题和整数分解问题$就是NP中间问题的例子。这几个是极少数几个还不清楚是否属于P类或NP完全类问题的NP类问题，。

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.^[20] If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level.^[21] Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai, runs in quasi-polynomial time.^[22]

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai, runs in quasi-polynomial time.

图同构问题是判定两个有限图是否同构的计算问题。复杂性理论中一个尚未解决的重要问题是图的同构问题是P类、NP完全类还是NP中间类问题。虽然答案还未揭晓，但是人们相信这个问题至少不是NP完全类问题。$如果图的同构确实是NP完全类的，则多项式时间层级塌缩到第二层。由于人们普遍认为 PH 不会塌缩到任何有限层，因此人们认为图的同构不是NP完全的。当前最佳的算法由芝加哥大学科学家拉斯洛·巴拜在2015年提出，他的算法是在拟多项式时间解决图的同构问题的。$

The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP^[23]). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes expected time

The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UPLance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes expected time

整数分解问题的核心在于求一个已知整数的质因数分解。它可以被认为是一个决策问题，其核心是判断输入的因子是否小于k。至今我们还未发现一个有效的整数分解算法，这也因此促成了现代密码系统的基础，比如RSA算法。整数分解问题是NP类问题和co-NP类问题，如果它也是NP完全的，多项式时间层次将崩溃到它的第一个层次(即，NP = co-NP)。整数分解最著名的算法是普通数域筛选法算法，它需要预期时间是

[math]\displaystyle{ O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right ) }[/math]

O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )

O left (exp left (left (left (left (tfrac {64n }{9} log (2) right) ^ { frac {1}{3} left (log (n log (2)) right) ^ { frac {2}{3} right))

to factor an n-bit integer. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time, although this does not indicate where the problem lies with respect to non-quantum complexity classes.

来分解一个n比特的整数。不过解决此问题最著名的量子Shor算法虽然在多项式时间内运行的，但这无法推断其在非量子复杂性问题中的位置。（翻译到此）

不知道属于P还是NP完全的NP问题

1975年，理查德·E·拉德纳（Richard E.Ladner）证明了如果 P ≠ NP 那么在NP中存在既不是P也不是NP完全的问题。^[19]这类问题称为NP中间问题。图同构问题、离散对数问题和整数分解问题是NP中间问题的例子。它们是为数不多的不知道属于P还是NP完全的NP问题。

图同构问题是计算两个有限图是否同构。复杂度理论中一个尚未解决的重要问题是，图同构问题是P、NP完全还是NP中间？答案不得而知，但人们相信它至少不是NP完全问题。^[20]如果图同构是NP完全的，则多项式时间层次结构将退化到第二层。^[21]由于人们普遍认为多项式层次结构不会退化到任何有限层次，因此人们认为图同构不是NP完全的。László Babai认为这个问题的最佳算法在近似多项式时间内运行。^[22]

整数分解问题是将给定整数分解成素数的计算问题。作为判定问题，它要判断输入是否有一个小于k的因子。目前还没有有效的整数分解算法，这一事实是几种现代密码系统的基础，例如RSA算法。整数分解问题出现在NP和co-NP中（甚至出现在UP和co-UP中^[23]）。如果这是NP完全问题，多项式时间层次结构将退化到第一层（即NP=co-NP）。目前最有效的整数分解算法是广义数字域筛选算法，它分解n比特整数预期需要的时间为

[math]\displaystyle{ O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right ) }[/math]

这个问题目前最好的量子算法——Shor算法，是多项式时间算法，尽管这并不能说明非量子复杂性类的问题所在。【没有懂这节最后一句话although this does not indicate where the problem lies with respect to non-quantum complexity classes.】

Does P mean "easy"?

文件:KnapsackEmpComplexity.GIF

The graph shows the running time vs. problem size for a knapsack problem of a state-of-the-art, specialized algorithm. The quadratic fit suggests that the algorithmic complexity of the problem is O((log(n))²).^[24]

All of the above discussion has assumed that P means "easy" and "not in P" means "difficult", an assumption known as Cobham's thesis. It is a common and reasonably accurate^{[citation needed]} assumption in complexity theory; however, it has some caveats.

All of the above discussion has assumed that P means "easy" and "not in P" means "difficult", an assumption known as Cobham's thesis. It is a common and reasonably accurate assumption in complexity theory; however, it has some caveats.

= = p 是“容易”的意思吗？= = 所有上述讨论都假定 p 意味着“容易”，而“不在 p 中”意味着“困难”，这一假设被称为 Cobham 的论点。在复杂性理论中，这是一个常见且相当准确的假设; 然而，它也有一些警告。

First, it is not always true in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, thus rendering it impractical. For example, the problem of deciding whether a graph G contains H as a minor, where H is fixed, can be solved in a running time of O(n²),^[25] where n is the number of vertices in G. However, the big O notation hides a constant that depends superexponentially on H. The constant is greater than [math]\displaystyle{ 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) }[/math] (using Knuth's up-arrow notation), and where h is the number of vertices in H.^[26]

First, it is not always true in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, thus rendering it impractical. For example, the problem of deciding whether a graph G contains H as a minor, where H is fixed, can be solved in a running time of O(n2), where n is the number of vertices in G. However, the big O notation hides a constant that depends superexponentially on H. The constant is greater than 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) (using Knuth's up-arrow notation), and where h is the number of vertices in H.

首先，这在实践中并不总是正确的。一个理论上的多项式算法可能有非常大的常数因子或指数，从而使其不切实际。例如，判断一个图 g 是否包含 h 作为一个次项，其中 h 是固定的，这个问题可以在 o (n2)的运行时间内解决，其中 n 是 g 的顶点数。这个常数大于2个上行上行(2个上行上行(2个上行上行(h/2)))(使用 Knuth 的上箭头表示法) ，其中 h 是 h 中的顶点数。

On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to tackling the problem in practice. There are algorithms for many NP-complete problems, such as the knapsack problem, the traveling salesman problem and the Boolean satisfiability problem, that can solve to optimality many real-world instances in reasonable time. The empirical average-case complexity (time vs. problem size) of such algorithms can be surprisingly low. An example is the simplex algorithm in linear programming, which works surprisingly well in practice; despite having exponential worst-case time complexity, it runs on par with the best known polynomial-time algorithms.^[27]

On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to tackling the problem in practice. There are algorithms for many NP-complete problems, such as the knapsack problem, the traveling salesman problem and the Boolean satisfiability problem, that can solve to optimality many real-world instances in reasonable time. The empirical average-case complexity (time vs. problem size) of such algorithms can be surprisingly low. An example is the simplex algorithm in linear programming, which works surprisingly well in practice; despite having exponential worst-case time complexity, it runs on par with the best known polynomial-time algorithms.

另一方面，即使一个问题被证明是 NP 完全的，即使 p 不等于 NP，在实践中仍然可能有有效的方法来解决这个问题。有许多 np 完全问题的算法，如背包问题问题、旅行商问题和布尔可满足性问题问题，这些算法可以在合理的时间内解决许多现实世界的实例。这类算法的经验平均案例复杂度(时间与问题大小)可能低得惊人。一个例子是位于单纯形法的线性规划，它在实际中运行得出奇的好; 尽管它具有指数最坏情况下的时间复杂度，但它与最著名的多项式时间算法运行得不相上下。

Finally, there are types of computations which do not conform to the Turing machine model on which P and NP are defined, such as quantum computation and randomized algorithms.

最后，还有一些不符合图灵机模型的计算，例如量子计算和随机算法。

P意味着“容易”？

以上所有讨论都假设P意味“容易”，而“不在P中”意味着“困难”，这一假设称为科巴姆（Cobham）论点。这是复杂性理论中一个常见且相当合理的假设；但需要注意一些事情。

首先，这在实际中并不总是正确的。理论上，多项式算法可能有非常大的常数因子或指数项，这时假设失效。例如，判定一个图G是否包含子图H，其中H是确定的。该问题可以在O(n²)的运行时间内解决，^[25]其中n是G中的顶点数，大O表示法隐藏了一个以超指数形式依赖于H的常数。该常数大于[math]\displaystyle{ 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) }[/math]（使用Knuth的上箭头表示法），其中h是H中的顶点数。^[26]

另一方面，即使一个问题被证明是NP完全的并且P ≠ NP，在实际中仍然可能有高效的方法来解决这个问题。许多NP完全问题，如背包问题、旅行商问题和布尔可满足性问题，都有算法可以在合理的时间得到最优解。这类算法的平均复杂度（时间与问题规模大小）可能低得出奇。线性规划中的单纯形法就是这样一个例子，它在实际中的表现出奇地好，与已知最好的算法一样是多项式时间算法，尽管在最坏情况下的时间复杂度是指数级的。^[27]

最后，还有一些类型的计算比如量子计算和随机算法不符合图灵机模型，P和NP是在图灵机模型上定义的，。

Reasons to believe P ≠ NP or P = NP

Cook provides a restatement of the problem in THE P VERSUS NP PROBLEM as: Does P = NP ?.According to polls,^[8]most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.

Cook provides a restatement of the problem in THE P VERSUS NP PROBLEM as: Does P = NP ?. According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.

= = 有理由相信 p ≠ NP 或 p = NP = = Cook 重述了《 P/NP问题的问题: p = NP 吗？.根据民意调查，大多数计算机科学家认为 p 不等于 NP。这种看法的一个关键原因是，在对这些问题进行了几十年的研究之后，还没有人能够为3000多个重要的已知 np 完全问题(见 np 完全问题列表)找到一个多项式时间算法。这些算法在 np- 完全性的概念被定义之前很久就已经被研究过了(第一个发现的 Karp 的21个 np- 完全问题，在它们被证明是 np- 完全的时候都是众所周知的存在问题)。此外，p = NP 的结果可能意味着许多其他目前被认为是错误的令人吃惊的结果，例如 NP = co-NP 和 p = ph。

It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience., point 9.

也有人直观地认为，存在着一些难以解决但解决方法很容易验证的问题，这些问题与现实世界的经验是一致的。

On the other hand, some researchers believe that there is overconfidence in believing P ≠ NP and that researchers should explore proofs of P = NP as well. For example, in 2002 these statements were made:^[8] /* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

} /* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

On the other hand, some researchers believe that there is overconfidence in believing P ≠ NP and that researchers should explore proofs of P = NP as well. For example, in 2002 these statements were made:

另一方面，一些研究者认为相信 p 不等于 NP 存在过度自信，研究者也应该探索 p = NP 的证明。例如，在2002年，这些声明是:

认为P ≠ NP 或 P = NP的原因

库克将P与NP问题重述为：P = NP吗？^[28]根据民意调查的结果，^[8]^[29]大多数计算机科学家认为P ≠ NP。这种观点的一个主要原因是，经过对这些问题几十年的研究，没有人能够为已知的3000多个重要的NP完全问题找到任何一种多项式时间算法（参见NP完全问题列表）。早在NP完全性的概念被定义之前，人们就开始寻找这些算法（在最早发现的NP完全问题中，卡普（Karp）的21个问题是当时非常知名的NP问题）。此外，P = NP意味着许多其他惊人的结论，而这些结论目前被认为是错误的，例如NP = co-NP和P = PH。

也有人凭直觉认为，这些难以求解但找到解后易于验证的问题，它们的存在与现实世界的经验相符。^[30]

如果P=NP，那么这个世界将是一个与我们通常认为的完全不同的地方。“创造性飞跃”没有特别的价值，在解决问题和发现解决方法之间没有巨大的鸿沟。
— 斯科特·阿伦森，得克萨斯大学奥斯汀分校（Scott Aaronson, UT Austin）

另一方面，一些研究人员认为，人们过于相信P ≠ NP了，研究人员也应该探索P = NP的证明。例如，2002年有如下观点：^[8]

支持P ≠ NP主要是因为在穷举搜索领域缺乏重大进展。在我看来，这是一个非常薄弱的论点。算法的搜索空间非常大，我们才刚刚开始探索。[...] 费马最后定理的证明也表明，非常简单的问题只能通过非常深刻的理论来解决。
— 莫斯·Y·瓦迪，莱斯大学（Moshe Y. Vardi, Rice University）
依靠猜测指导研究计划并不好。每个问题都应该尝试两个方向。偏见导致著名数学家未能解决那些方法与其预期相反的著名问题，尽管他们已经开发出了所需的所有方法。
— 安尼尔·内罗德，康奈尔大学（Anil Nerode, Cornell University）

Consequences of solution

One of the reasons the problem attracts so much attention is the consequences of the some possible answers. Either direction of resolution would advance theory enormously, and perhaps have huge practical consequences as well.

这个问题之所以如此引人注目的原因之一是某些可能答案的后果。任何一种解决方案都将极大地促进理论的发展，也许还会产生巨大的实际后果。

P = NP

A proof that P = NP could have stunning practical consequences if the proof leads to efficient methods for solving some of the important problems in NP. The potential consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.

= = = p = NP = = = = 证明 p = NP 可以有惊人的实际结果，如果证明导致有效的方法来解决一些重要问题在 NP。由于各种 np 完全问题在许多领域都具有根本性的意义，所以潜在的结果，无论是正面的还是负面的，都会出现。

It is also very possible that a proof would not lead to practical algorithms for NP-complete problems. The formulation of the problem does not require that the bounding polynomial be small or even specifically known. A non-constructive proof might show a solution exists without specifying either an algorithm to obtain it or a specific bound. Even if the proof is constructive, showing an explicit bounding polynomial and algorithmic details, if the polynomial is not very low-order the algorithm might not be sufficiently efficient in practice. In this case the initial proof would be mainly of interest to theoreticians, but the knowledge that a polynomial time solutions are possible would surely spur research into better (and possibly practical) methods to achieve them.

It is also very possible that a proof would not lead to practical algorithms for NP-complete problems. The formulation of the problem does not require that the bounding polynomial be small or even specifically known. A non-constructive proof might show a solution exists without specifying either an algorithm to obtain it or a specific bound. Even if the proof is constructive, showing an explicit bounding polynomial and algorithmic details, if the polynomial is not very low-order the algorithm might not be sufficiently efficient in practice. In this case the initial proof would be mainly of interest to theoreticians, but the knowledge that a polynomial time solutions are possible would surely spur research into better (and possibly practical) methods to achieve them.

一个证明也很有可能不会导致 np- 完全问题的实用算法。这个问题的表达式不要求边界多项式很小，甚至不需要特别知道。非构造性证明可能表明解的存在，而不指定获得解的算法或特定界限。即使证明是构造性的，显示了明确的包围多项式和算法细节，如果多项式的阶数不是很低，算法在实践中可能不够有效。在这种情况下，初始证明主要是理论家感兴趣的，但是多项式时间解决方案是可能的这一知识肯定会促使人们研究更好的(可能是实用的)方法来实现它们。

An example of a field that could be upended by a solution showing P = NP is cryptography, which relies on certain problems being difficult. A constructive and efficient solution^{[Note 2]} to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:

Existing implementations of public-key cryptography,^[31] a foundation for many modern security applications such as secure financial transactions over the Internet.
Symmetric ciphers such as AES or 3DES,^[32] used for the encryption of communications data.
Cryptographic hashing, which underlies blockchain cryptocurrencies such as Bitcoin, and is used to authenticate software updates. For these applications, the problem of finding a pre-image that hashes to a given value must be difficult in order to be useful, and ideally should require exponential time. However, if P = NP, then finding a pre-image M can be done in polynomial time, through reduction to SAT.^[33]

These would need to be modified or replaced by information-theoretically secure solutions not inherently based on P-NP inequivalence.

An example of a field that could be upended by a solution showing P = NP is cryptography, which relies on certain problems being difficult. A constructive and efficient solutionExactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of O(N^2) with a reasonable constant term would be disastrous. On the other hand, a solution that is \Omega(N^4) in almost all cases would not pose an immediate practical danger. to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:

Existing implementations of public-key cryptography,See for a reduction of factoring to SAT. A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses. a foundation for many modern security applications such as secure financial transactions over the Internet.
Symmetric ciphers such as AES or 3DES,See, for example, in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size. used for the encryption of communications data.
Cryptographic hashing, which underlies blockchain cryptocurrencies such as Bitcoin, and is used to authenticate software updates. For these applications, the problem of finding a pre-image that hashes to a given value must be difficult in order to be useful, and ideally should require exponential time. However, if P = NP, then finding a pre-image M can be done in polynomial time, through reduction to SAT.

These would need to be modified or replaced by information-theoretically secure solutions not inherently based on P-NP inequivalence.

密码学就是这样一个例子，一个字段可以被显示 p = NP 的解所颠倒，这个例子就是密码学，它依赖于某些困难的问题。一个有建设性和有效率的解决方案一个解决方案对密码学造成威胁的效率究竟有多高取决于细节。用一个合理的常数项求 o (n ^ 2)的解将是灾难性的。另一方面，一个在几乎所有情况下都是欧米茄(n ^ 4)的解决方案不会构成直接的实际危险。一个 np 完全问题，如3-SAT 将破坏大多数现有的密码系统，包括:

现有的实现的公开密钥加密，请看一个因数化为 SAT。一个512位因式分解问题(因式分解后为8400mips 年)转化为一个由63,652个变量和406,860个子句组成的 SAT 问题。是许多现代安全应用的基础，例如通过互联网进行安全的金融交易。
对称密码，例如 AES 或3des---- 例如，将 DES 的一个实例编码为具有10336个变量和61935个子句的 SAT 问题。一个3des 问题实例大约是这个大小的3倍。用来加密通讯数据。
加密哈希，是区块链加密货币(如比特币)的基础，用于验证软件更新。对于这些应用程序，要找到一个散列到给定值的预映像一定很困难，而且理想情况下应该需要 EXPTIME。然而，如果 p = NP，则可以在多项式时间内找到一个前图像 m，通过简化到 SAT。这些将需要修改或取代的信息-理论上安全的解决方案不固有地基于 P-NP 不对等。

On the other hand, there are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming and the travelling salesman problem. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction, are also NP-complete;^[34] if these problems were efficiently solvable, it could spur considerable advances in life sciences and biotechnology.

On the other hand, there are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming and the travelling salesman problem. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction, are also NP-complete; if these problems were efficiently solvable, it could spur considerable advances in life sciences and biotechnology.

另一方面，如果将许多目前在数学上难以处理的问题变得易于处理，将会产生巨大的积极影响。例如，运筹学中的许多问题都是 np 完全问题，比如某些类型的整数规划和旅行推销员问题。这些问题的有效解决方案将对物流产生巨大的影响。许多其他重要问题，如蛋白质结构预测中的一些问题，也是 np 完全问题; 如果这些问题能够有效地解决，它将促进生命科学和生物技术的相当大的进步。

But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:History of this letter and its translation from From pages 359–376 of Optimization Stories, M. Grötschel (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.

Similarly, Stephen Cook (assuming not only a proof, but a practically efficient algorithm) says

但是这样的变化与数学本身引起的解决 np 完全问题的有效方法的革命相比，可能没有什么意义。哥德尔在他早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械方法将彻底改变数学: 这封信的历史及其翻译自《优化故事》第359-376页，m. Grötschel (编辑) ，一本2012年8月出版并分发给在柏林举行的第21届国际数学编程研讨会的数学文献。同样，斯蒂芬 · 库克(假设不仅是一个证明，而且是一个实际有效的算法)说

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated—for instance, Fermat's Last Theorem took over three centuries to prove. A method that is guaranteed to find proofs to theorems, should one exist of a "reasonable" size, would essentially end this struggle.

研究领域的数学家们毕生致力于证明定理，有些证明甚至需要几十年甚至几百年的时间才能找到，例如，费马最后定理的证明花了三个多世纪。如果存在一种“合理”规模的方法，那么这种方法就能保证找到定理的证明，从本质上结束这种斗争。

Donald Knuth has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof{{quote|1=[...] if you imagine a number M that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do n^M bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.

Donald Knuth has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof: /* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

然而，我的主要观点是，我不相信即使证明了 p = NP 等式也会有帮助，因为这样的证明几乎肯定是非建设性的

P ≠ NP

A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.

= = = = p ≠ NP = = = 证明 p ≠ NP 缺乏证明 p = NP 的实际计算效益，但仍代表了计算复杂性理论的一个重大进展，并为未来的研究提供了指导。这将使人们能够以正式的方式表明许多共同的问题无法有效地解决，从而使研究人员的注意力能够集中在其他问题的部分解决或解决方案上。由于人们普遍相信 p 不等于 NP，这种研究的焦点大部分已经开始了。

Also P ≠ NP still leaves open the average-case complexity of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. Russell Impagliazzo has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question. These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A Princeton University workshop in 2009 studied the status of the five worlds.

Also P ≠ NP still leaves open the average-case complexity of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable. Russell Impagliazzo has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995 These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A Princeton University workshop in 2009 studied the status of the five worlds.

而且 p ≠ NP 仍然保留了 NP 难题的平均格式复杂性。例如，在最坏的情况下，SAT 可能需要一个 EXPTIME，但几乎所有随机选择的实例都是有效可解的。Russell Impagliazzo 描述了五个假设的“世界”，这些世界可能由不同的可能解决方案和平均案例复杂性问题所产生。Impagliazzo，“ a personal view of average-case Complexity,”SCT，pp. 134,10 th Annual Structure in Complexity Theory Conference (SCT’95) ，1995这些范围从“算法米卡”(algorithm mica) ，其中 p = NP 和 SAT 等问题在所有情况下都可以有效地解决，到“ Cryptomania”，其中 p ≠ NP，生成 p 以外问题的硬实例很容易，有三种中间可能性反映 NP 困难实例的不同可能分布。本文把 p 不等于 NP 但 NP 中所有问题在一般情况下都是易处理的“世界”称为“启发式问题”。2009年，普林斯顿大学的一个研讨会研究了五个世界的状态。

不同结论的影响

这个问题吸引这么多关注的原因之一是因为潜在结论带来的重大影响。任何一种解决方法的思路都会极大地推动理论进展，或许也会因此产生巨大影响。

P = NP

如果P = NP的证明能为NP中的一些重要问题提供高效的方法，那么该证明会有惊人的影响。由于许多不同的NP完全问题在许多领域意义重大，这产生了潜在的或积极或消极的影响。

证明的结果可能也不会带来NP完全问题的实用算法。该问题的解答不要求多项式的边界很小甚至被明确知道。一个没有贡献的证明可以避开该算法或多项式边界来证明一个解的存在。即使证明是有贡献的，其提供了明确的多项式边界和算法细节，如果多项式不是非常低阶的，那么算法在实际中可能不够有效。在这种情况下，理论学家主要会对最初的证明感兴趣，而认识到多项式时间解的可能性将会推动研究找到更好（可能实际有效）的方法。

一个领域可以被P = NP的证明结果颠覆的例子是密码学，它的基石是某些难解的问题。对于3-SAT这样的NP完全问题，一个有贡献且高效的算法^{[注 2]}将颠覆大多数现有的密码系统，包括：

现有公钥密码的实现，^[31]它是当代许多安全应用的基础，比如网上安全金融交易。
用于通信数据加密的对称密码，比如AES或3DES^[32]。
哈希加密，它是比特币等区块链加密货币的基础，用于验证软件更新。对于这些应用程序，要想找到一个有用的映射到给定值的预映像是很困难的，而且理想情况下需要指数级的时间。但如果P = NP，则可以在多项式时间内通过归约为SAT来找到预映像M。^[33]

这些需要被信息理论安全方法修改或替换的密码系统潜在的基于P-NP不等性。

另一方面，许多目前在数学上棘手的问题会变得容易处理。例如，运筹学中的许多问题都是NP完全的，比如某些类型的整数规划和旅行商问题。有效解决这些问题将对物流业产生巨大影响。许多其他的重要问题，如蛋白质结构预测，也是NP完全的；^[34]如果这些问题能得到有效解决，就可以促进生命科学和生物技术的长足进步。

但这种变化的重要性与解决NP完全问题的有效方法本身给数学引发的革命相比就相形见绌了。哥德尔（Gödel）在其早期关于计算复杂性的思想中指出，一种可以解决任何问题的机械式方法将彻底改变数学：^[35]^[36]

如果真的有一台机器的φ(n)∼ k⋅ n（甚至∼ k⋅ n²），这将产生重大影响。也就是说，这意味着，尽管决策问题（Entscheidungsproblem）是不可判定的，数学家的脑力劳动依然完全可以被机器取代。毕竟，人们只需要选择一个足够大的自然数n使得机器无法给出结果时，因而就没有必要再考虑这个问题了。【没看懂，该节】

类似地，斯蒂芬·库克（假设不仅是一个证明，而且是一个实际有效的算法）说^[28]

... 这使计算机找到任何一个定理的证明过程成为可能，而且因为证明过程能在多项式时间内验证，所以证明过程的长度也是能够接受的。这将改变数学。例题可能包括CMI奖中的所有问题。

数学家在他们的职业生涯中一直在证明定理，有些证明在问题提出后的几十年甚至几个世纪才找到。例如，费马最后定理经过三个多世纪才得到证明。如果有一种方法能够保证找到定理的证明，并且其规模“合理”，那么这种方法将从根本上结束这场斗争。唐纳德·克努特（Donald Knuth）表示，他已经开始相信P = NP，但对可能的证明结果所带来的影响仍持保留态度：^[37]

[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可行的算法对n个给定的比特进行n^M位加法或移位运算，很难相信所有这些算法都失败了。因而我的主要观点是，即使等式P = NP被证明了，我也不相信它会有什么用，因为这样的证明几乎肯定是没有贡献的。

P ≠ NP

证明P ≠ NP跟证明P = NP相比缺乏实际计算优势，但它代表了计算复杂性理论的一个重大进步，并可以对未来的研究提供指导。这将使人们能够以一种严格的方式证明，许多常见问题无法有效解决，因此研究人员可以专注于求出部分解或解其他问题。由于人们普遍相信P ≠ NP，大部分研究已经聚焦于此。^[38]

P ≠ NP仍然保留着NP中困难问题的平均复杂度。例如，SAT在最坏的情况下可能需要指数级的时间，但几乎所有随机选择的实例都可以有效解决。拉塞尔·英帕利亚佐（Russell Impagliazzo）描述了五个假设的“世界”，这五个“世界”源于对平均复杂性问题的不同可能回答。^[39]范围从“算法”（Algorithmica）世界，这个世界中 P = NP 和像 SAT 这样的问题中的所有例子都可以有效解决，到“密码狂热”（Cryptomania）世界，这个世界是 P ≠ NP 并且容易生成在 P 之外的困难问题，其中有着三种可能性，它们反映了NP难问题中不同可能的难度分布。【没看懂，这节的第二段倒数第三句with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. 】在这篇论文中，“启发式”（Heuristica）是这样一个“世界”，P ≠ NP但NP中的大部分问题都是比较容易解决的。2009年，普林斯顿大学的一个研讨会研究了五个世界的现状。^[40]

Results about difficulty of proof

Although the P = NP problem itself remains open despite a million-dollar prize and a huge amount of dedicated research, efforts to solve the problem have led to several new techniques. In particular, some of the most fruitful research related to the P = NP problem has been in showing that existing proof techniques are not powerful enough to answer the question, thus suggesting that novel technical approaches are required.

尽管获得了一百万美元的奖金和大量的专门研究，但是 p = NP 问题本身仍然是一个悬而未决的问题，解决这个问题的努力产生了一些新的技术。特别是，一些与 p = NP 问题相关的最有成效的研究已经表明现有的证明技术不足以回答这个问题，因此表明需要新的技术方法。

As additional evidence for the difficulty of the problem, essentially all known proof techniques in computational complexity theory fall into one of the following classifications, each of which is known to be insufficient to prove that P ≠ NP:

Classification	Definition
Relativizing proofs	Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an oracle (a black box which can answer a fixed set of questions in constant time, such as a black box that solves any given traveling salesman problem in 1 step), and the running time of the oracle is not counted against the running time of the algorithm. Most proofs (especially classical ones) apply uniformly in a world with oracles regardless of what the oracle does. These proofs are called relativizing. In 1975, Baker, Gill, and Solovay showed that P = NP with respect to some oracles, while P ≠ NP for other oracles.^[41] Since relativizing proofs can only prove statements that are uniformly true with respect to all possible oracles, this showed that relativizing techniques cannot resolve P = NP.
Natural proofs	In 1993, Alexander Razborov and Steven Rudich defined a general class of proof techniques for circuit complexity lower bounds, called natural proofs.^[42] At the time all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P = NP. However, Razborov and Rudich showed that, if one-way functions exist, then no natural proof method can distinguish between P and NP. Although one-way functions have never been formally proven to exist, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can resolve P = NP.
Algebrizing proofs	After the Baker-Gill-Solovay result, new non-relativizing proof techniques were successfully used to prove that IP = PSPACE. However, in 2008, Scott Aaronson and Avi Wigderson showed that the main technical tool used in the IP = PSPACE proof, known as arithmetization, was also insufficient to resolve P = NP.^[43]

As additional evidence for the difficulty of the problem, essentially all known proof techniques in computational complexity theory fall into one of the following classifications, each of which is known to be insufficient to prove that P ≠ NP:

Classification	Definition
Relativizing proofs	Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an oracle (a black box which can answer a fixed set of questions in constant time, such as a black box that solves any given traveling salesman problem in 1 step), and the running time of the oracle is not counted against the running time of the algorithm. Most proofs (especially classical ones) apply uniformly in a world with oracles regardless of what the oracle does. These proofs are called relativizing. In 1975, Baker, Gill, and Solovay showed that P = NP with respect to some oracles, while P ≠ NP for other oracles. Since relativizing proofs can only prove statements that are uniformly true with respect to all possible oracles, this showed that relativizing techniques cannot resolve P = NP.
Natural proofs	In 1993, Alexander Razborov and Steven Rudich defined a general class of proof techniques for circuit complexity lower bounds, called natural proofs. At the time all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P = NP. However, Razborov and Rudich showed that, if one-way functions exist, then no natural proof method can distinguish between P and NP. Although one-way functions have never been formally proven to exist, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can resolve P = NP.
Algebrizing proofs	After the Baker-Gill-Solovay result, new non-relativizing proof techniques were successfully used to prove that IP = PSPACE. However, in 2008, Scott Aaronson and Avi Wigderson showed that the main technical tool used in the IP = PSPACE proof, known as arithmetization, was also insufficient to resolve P = NP.

作为这个问题困难性的额外证据，基本上所有已知的证明方法都可以分为以下几类，每一类都不足以证明 p ≠ NP: { | class = “ wikable”|-！分类！定义 |-| 相对化证明 | 想象一个世界，在这个世界里，每个算法都被允许对称为 oracle 的固定子程序进行查询(一个黑盒子，它可以在固定的时间内回答一组固定的问题，例如一个黑盒子，它可以在一步内解决任何给定的旅行商问题) ，oracle 的运行时间不计算在算法的运行时间内。大多数证明(尤其是经典证明)统一地应用于一个有神谕的世界，而不管神谕做什么。这些证据被称为相对化。1975年，贝克、吉尔和索洛维指出，就某些预言而言，p = NP，而就其他预言而言，p ≠ NP。由于相对化证明只能证明对所有可能的神谕都一致正确的陈述，这表明相对化技术不能解决 p = NP。|-| 自然证明 | 1993年，亚历山大 · 拉兹博罗夫和史蒂文 · 鲁迪奇定义了一类通用的电路复杂度下界证明技术，称为自然证明。当时所有已知的电路下界都是自然的，电路复杂度被认为是解决 p = NP 的一个非常有前途的方法。然而，Razborov 和 ruditch 指出，如果存在单向函数，那么没有任何自然证明方法可以区分 p 和 NP。虽然单向函数从来没有被正式证明过存在，但大多数数学家相信它们存在，而且证明它们存在的证明比 p ≠ NP 要有力得多。因此，仅靠自然证明不大可能解决 p = NP。|-| 代数证明 | 在 Baker-Gill-Solovay 的结果之后，新的非相对化证明技术被成功地用来证明 IP = PSPACE。然而，在2008年，Scott Aaronson 和 Avi Wigderson 展示了用于 IP = PSPACE 证明的主要技术工具，也就是所谓的算术化，也不足以解决 p = NP。|}

These barriers are another reason why NP-complete problems are useful: if a polynomial-time algorithm can be demonstrated for an NP-complete problem, this would solve the P = NP problem in a way not excluded by the above results.

这些障碍是 NP 完全问题有用的另一个原因: 如果一个 NP 完全问题的多项式时间算法可以证明，这将解决 p = NP 问题的方式不排除上述结果。

These barriers have also led some computer scientists to suggest that the P versus NP problem may be independent of standard axiom systems like ZFC (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it is impossible to prove in ZFC that such algorithms are correct.^[44] However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the Peano axioms (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.^[45] Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

These barriers have also led some computer scientists to suggest that the P versus NP problem may be independent of standard axiom systems like ZFC (cannot be proved or disproved within them). The interpretation of an independence result could be that either no polynomial-time algorithm exists for any NP-complete problem, and such a proof cannot be constructed in (e.g.) ZFC, or that polynomial-time algorithms for NP-complete problems may exist, but it is impossible to prove in ZFC that such algorithms are correct.. However, if it can be shown, using techniques of the sort that are currently known to be applicable, that the problem cannot be decided even with much weaker assumptions extending the Peano axioms (PA) for integer arithmetic, then there would necessarily exist nearly-polynomial-time algorithms for every problem in NP.. Therefore, if one believes (as most complexity theorists do) that not all problems in NP have efficient algorithms, it would follow that proofs of independence using those techniques cannot be possible. Additionally, this result implies that proving independence from PA or ZFC using currently known techniques is no easier than proving the existence of efficient algorithms for all problems in NP.

这些障碍也导致一些计算机科学家提出，P/NP问题可能独立于标准公理系统，如 ZFC (无法在其中被证明或否定)。对独立性结果的解释可以是对任何 np 完全问题都不存在多项式时间算法，这样的证明不能在(例如)中构造在 ZFC 中，np- 完全问题的多项式时间算法可能存在，但在 ZFC 中不可能证明这些算法是正确的。.然而，如果能够证明，使用目前已知适用的排序技术，即使将 Peano 整数算术公理(PA)扩展到更弱的假设，也无法决定问题，那么 NP 中的每个问题都必然存在近多项式时间算法。.因此，如果有人相信(正如大多数复杂性理论家所做的那样)并非所有 NP 问题都有高效算法，那么可以推断，用这些技术证明独立性是不可能的。此外，这个结果意味着用目前已知的技术证明独立于 PA 或 ZFC 并不比证明 NP 中所有问题的有效算法的存在更容易。

关于证明难度的结果

P = NP问题仍然还未解决，虽然它有着100万美元的奖金并且有大量专门的研究，以及为了解决这个问题已经产生了几种新技术。尤其是与P=NP问题相关的一些最富有成效的研究表明，现有的证明技术不足以解决这个问题，因此意味着需要新的技术方法。

作为额外表现问题困难的证据，计算复杂性理论中的所有已知的证明技术基本上都属于以下类别，它们都无法有力证明P ≠ NP:

分类	定义
相对证明	想象这样一个世界，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有oracle的世界，无论oracle做什么。这被称为相对证明。1975年，贝克（Baker）、吉尔（Gill）和索洛维（Solovay）证明，对于某些oracle，P = NP，而对于其他oracle，P ≠ NP。^[41]由于相对证明只能证明对所有可能的oracle都一致正确的陈述，这表明相对证明技术无法解决P = NP。
自然证明	1993年，亚历山大·拉兹博罗夫（Alexander Razborov）和史蒂文·鲁迪奇（Steven Rudich）为电路复杂度下限定义了一类通用的证明技术，称为自然证明。^[42]当时，所有已知的电路下界都是自然的，电路复杂性被认为是解决P = NP的一种非常有前途的方法。然而拉兹博罗夫（Razborov）和鲁迪奇（Razich）证明如果单向函数存在，那么没有一种自然证明法可以区分P和NP。虽然单向函数从未被正式证明存在，但大多数数学家认为它们确实存在，并且它们存在性的证明将比P ≠ NP强的多。因此，仅用自然证明不太可能解决P = NP。
代数证明	在Baker-Gill-Solovay结果之后，新的非相对证明技术被成功地用于证明IP = PSPACE。然而，在2008年，斯科特·阿伦森（Scott Aaronson）和阿维·维格德森（Avi Wigderson）证明了在IP = PSPACE证明中使用的主要技术工具，即所谓的算术化，也不足以解决P = NP问题。^[43]

这些障碍是NP完全问题有用的另一个原因：如果NP完全问题有多项式时间算法，这将以不被以上结果排除的方式解决P=NP问题。

这些障碍还导致一些计算机科学家提出，P/NP问题可能独立于ZFC等标准公理系统（无法在其中被证明或证伪）。对独立性结果的解释可能是，要么任何NP完全问题都不存在多项式时间算法，这样的证明无法在（比如说）ZFC中构建，要么NP完全问题的多项式时间算法可能存在，但在ZFC中不可能证明这样的算法是正确的。^[44]然而，如果可以使用目前已知的适用技术，那么可以证明即使在较弱假设下扩展了整数运算的Peano公理（PA）下，问题也无法判定，那么NP中的每个问题都必然存在近似多项式时间算法。^[45]因此，如果一个人认为（正如大多数复杂性理论家所做的那样）并非NP中的所有问题都有高效的算法，那么使用这些技术证明独立性是不可能的。此外，这一结果表明，使用目前已知的技术在PA或ZFC中证明独立性并不比证明NP中所有问题存在高效算法容易。

Claimed solutions

While the P versus NP problem is generally considered unsolved,^[46] many amateur and some professional researchers have claimed solutions. Gerhard J. Woeginger maintains a list that, as of 2016, contains 62 purported proofs of P = NP, 50 proofs of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable.^[47] Some attempts at resolving P versus NP have received brief media attention,^[48] though these attempts have since been refuted.

While the P versus NP problem is generally considered unsolved, many amateur and some professional researchers have claimed solutions. Gerhard J. Woeginger maintains a list that, as of 2016, contains 62 purported proofs of P = NP, 50 proofs of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable. Some attempts at resolving P versus NP have received brief media attention, though these attempts have since been refuted.

虽然 P/NP问题通常被认为是未解之谜，但许多业余爱好者和一些专业研究人员已经宣称了解决方案。2016年，Gerhard j. Woeginger 提出了一个列表，其中包含了62个 p = NP 的声称证明，50个 p ≠ NP 的证明，2个证明这个问题是不可证明的，还有一个证明它是不可判定的。解决 p 与 NP 问题的一些尝试受到了媒体的短暂关注，尽管这些尝试已被驳斥。

声称的解答

虽然P/NP问题通常被认为是不可解决的，^[46]许多业余和一些专业研究人员声称提出了解决方法。格哈德·J·沃金（Gerhard J.Woeginger）维护着一份列表，截至2016年，该表包含62个据称是P = NP的证明，50个P ≠ NP的证明，2个问题不可证明的证明，1个问题不可判定的证明。^[47]一些试图解决P/NP的尝试得到了媒体的短暂关注，^[48]尽管这些尝试后来遭到了反驳。

Logical characterizations

The P = NP problem can be restated in terms of expressible certain classes of logical statements, as a result of work in descriptive complexity.

由于描述性复杂性的工作，p = NP 问题可以用可表述的某些类别的逻辑陈述来重述。

Consider all languages of finite structures with a fixed signature including a linear order relation. Then, all such languages in P can be expressed in first-order logic with the addition of a suitable least fixed-point combinator. Effectively, this, in combination with the order, allows the definition of recursive functions. As long as the signature contains at least one predicate or function in addition to the distinguished order relation, so that the amount of space taken to store such finite structures is actually polynomial in the number of elements in the structure, this precisely characterizes P.

考虑具有包括线性顺序关系的固定签名的有限结构的所有语言。然后，所有这些语言在 p 中都可以用一阶逻辑表示，只要加上一个合适的最小不动点组合子。实际上，结合顺序，可以定义递归函数。只要签名除了特殊的顺序关系之外，还包含至少一个谓词或函数，因此用于存储这种有限结构的空间量实际上是多项式的，这正是 p 的特征。

Similarly, NP is the set of languages expressible in existential second-order logic—that is, second-order logic restricted to exclude universal quantification over relations, functions, and subsets. The languages in the polynomial hierarchy, PH, correspond to all of second-order logic. Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?".^[49] The word "existential" can even be dropped from the previous characterization, since P = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).

Similarly, NP is the set of languages expressible in existential second-order logic—that is, second-order logic restricted to exclude universal quantification over relations, functions, and subsets. The languages in the polynomial hierarchy, PH, correspond to all of second-order logic. Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?".Elvira Mayordomo. "P versus NP" Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004). The word "existential" can even be dropped from the previous characterization, since P = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).

类似地，NP 是一组可以用存在二阶逻辑表达的语言---- 也就是说，二阶逻辑限制排除关系、函数和子集上的全称量化。PH 的语言，PH，对应于所有的二阶逻辑。因此，问题“ p 是 NP 的一个适当子集”可以重新表述为“存在二阶逻辑能够描述语言(有限的线性有序结构与非平凡签名) ，一阶逻辑与最少不动点不能？“ Elvira Mayordomo。"P versus NP" Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).存在主义这个词甚至可以从前面的角色塑造中去掉，因为 p = NP 当且仅当 p = PH (正如前者建立 NP = co-NP，这反过来意味着 NP = PH)。

逻辑特征【过多逻辑学的专业词汇，我许多句子看不懂，编辑需要重点关注】

P = NP问题可以用可表达的特定类别的逻辑语句来重新表述，这是描述复杂性这项工作的结果。

用固定签名考虑包括线性次序关系的所有语言的有限结构。然后，通过添加合适的最小定点组合符，P中所有这些语言都可以用一阶逻辑表示。实际上，与次序相结合能定义递归函数。只要签名除了包含可分辨顺序关系之外，还至少有一个谓词或函数，那么存储此类有限结构所占用的空间量实际上是该结构中元素数量的多项式，这准确刻画了P。

类似地，NP是一组存在性二阶逻辑中可表达的语言，也就是强迫排除关系、函数和子集上的通用量化符的二阶逻辑。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，“P是NP的一个恰当子集吗”这个问题可以重述为“是否存在这样一种二阶逻辑，它能够描述（具有非平凡签名但有限线性有序结构的）语言，但具有最小定点的一阶逻辑不能？”。^[49]“存在”一词甚至可以从前面的描述中删除，因为P = NP当且仅当P = PH（因为前者将确定NP = co-NP，这进一步说明NP = PH）。

Polynomial-time algorithms

No algorithm for any NP-complete problem is known to run in polynomial time. However, there are algorithms known for NP-complete problems with the property that if P = NP, then the algorithm runs in polynomial time on accepting instances (although with enormous constants, making the algorithm impractical). However, these algorithms do not qualify as polynomial time because their running time on rejecting instances are not polynomial. The following algorithm, due to Levin (without any citation), is such an example below. It correctly accepts the NP-complete language SUBSET-SUM. It runs in polynomial time on inputs that are in SUBSET-SUM if and only if P = NP:

= = = 多项式时间算法 = = 任何 np 完全问题的算法都不能在多项式时间内运行。然而，对于 NP 完全问题，有一些已知的算法具有这样的性质: 如果 p = NP，那么算法在接受实例时运行在多项式时间内(尽管具有大量的常数，使得算法不切实际)。然而，这些算法不符合多项式时间，因为它们拒绝实例的运行时间不是多项式的。下面的算法就是这样一个例子，由于 Levin (没有引用)。它正确地接受 np 完全语言 SUBSET-SUM。当且仅当 p = NP:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

接受 np 完全语言 SUBSET-SUM 的//算法。///这是一个多项式时间算法当且仅当 p = NP。//“多项式时间”意味着当//答案应该是“是”时，它在多项式时间内返回“是”，当它是“否”时，它将永远运行下去。///Input: s = 一个有限的整数集//Output: “ yes”，如果 s 的任何子集合加起来等于0。//永远运行，否则没有输出。//注意: “程序号 m”是通过用二进制写整数 m 得到的程序，然后//考虑到这个字符串是一个//程序。每个可能的程序都可以这样//生成，尽管由于语法错误，大多数程序什么也不做//。对于 k = 1... ∞ FOR m = 1... k Run 程序数 m FOR k steps with input s 如果程序输出一列不同的整数，而且所有的整数都在 s 中，并且整数和为0 THEN OUTPUT“ yes”和 HALT

If, and only if, P = NP, then this is a polynomial-time algorithm accepting an NP-complete language. "Accepting" means it gives "yes" answers in polynomial time, but is allowed to run forever when the answer is "no" (also known as a semi-algorithm).

If, and only if, P = NP, then this is a polynomial-time algorithm accepting an NP-complete language. "Accepting" means it gives "yes" answers in polynomial time, but is allowed to run forever when the answer is "no" (also known as a semi-algorithm).

如果且仅当 p = NP，那么这是一个接受 NP 完全语言的多项式时间算法。“接受”意味着它在多项式时间内给出“是”的答案，但当答案是“否”时，它可以永远运行(也称为半算法)。

This algorithm is enormously impractical, even if P = NP. If the shortest program that can solve SUBSET-SUM in polynomial time is b bits long, the above algorithm will try at least $2 b - 1$ other programs first.

This algorithm is enormously impractical, even if P = NP. If the shortest program that can solve SUBSET-SUM in polynomial time is b bits long, the above algorithm will try at least other programs first.

即使 p = NP，这种算法也是极不实用的。如果能在多项式时间内求子集和的最短程序长度为 b 位，则上述算法至少要先尝试其他程序。

多项式时间算法

任何已知的NP完全问题都没有多项式时间运行的算法。但如果其满足P = NP这个性质，则该算法能以多项式时间接受实例（尽管常数项巨大，使得该算法不切实际）。尽管如此，这些算法并不是多项式时间的，因为它们在拒绝实例时的运行时间不是多项式时间。下面这个由Levin（没有任何引用）提出的算法就是这样一个例子。它能正确接受NP完全语言SUBSET-SUM。当且仅当P = NP，它对SUBSET-SUM的输入以多项式时间运行：

// 接受NP完全语言SUBSET-SUM的算法。
//
// 当且仅当 P = NP时，它是一个多项式时间算法。
//
// "多项式时间" 意味着当答案是"yes"时，它在多项式时间内返回 "yes"
// 当答案是"no"时，它一直运行。
//
// 输入: S = 有限的整数集合
// 输出: 如果S的任何一个子集求和为0，输出"yes"。
// 如果没有输出就一直运行。
// 注意: “M号程序”是通过将整数M以二进制形式表示，
// 然后将这些比特字符串视为一个程序得到的。
// 每一个可能的程序都可以通过这种方式生成，
// 尽管由于语法错误，大多数程序什么也不做。
FOR K = 1...∞
  FOR M = 1...K
    输入S，运行K步M号程序
    IF 程序输出一串不同的整数
      AND 所有整数都在S中
      AND 这些整数相加为0
    THEN
      OUTPUT "yes" and HALT

当且仅当P = NP，这是一个接受NP完全语言的多项式时间算法。“接受”意味着它在多项式时间内给出“是”的回答，但当回答为“否”时，它可以永远运行（也称为半算法）。

即使P = NP，这个算法也非常不实用。如果能在多项式时间内求解SUBSET-SUM的最短程序是b位长，则上述算法将首先至少尝试其他程序2^b− 1次。

Formal definitions

P and NP

Conceptually speaking, a decision problem is a problem that takes as input some string w over an alphabet Σ, and outputs "yes" or "no". If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) that can produce the correct answer for any input string of length n in at most cn^k steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is defined as the set of all languages that can be decided by a deterministic polynomial-time Turing machine. That is,

[math]\displaystyle{ \mathbf{P} = \{ L : L=L(M) \text{ for some deterministic polynomial-time Turing machine } M \} }[/math]

where

[math]\displaystyle{ L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \} }[/math]

and a deterministic polynomial-time Turing machine is a deterministic Turing machine M that satisfies the following two conditions:

Conceptually speaking, a decision problem is a problem that takes as input some string w over an alphabet Σ, and outputs "yes" or "no". If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) that can produce the correct answer for any input string of length n in at most cnk steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is defined as the set of all languages that can be decided by a deterministic polynomial-time Turing machine. That is,

\mathbf{P} = \{ L : L=L(M) \text{ for some deterministic polynomial-time Turing machine } M \}

where

L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}

and a deterministic polynomial-time Turing machine is a deterministic Turing machine M that satisfies the following two conditions:

= = = p 和 NP = = = 概念上来说，判定问题是一个将字符串 w 作为字母表 σ 上的输入，并输出“ yes”或“ no”的问题。如果有一个算法(比如说图灵机，或者一个具有无限内存的计算机程序)可以在最多的 cnk 步骤中为任意长度为 n 的输入字符串生成正确的答案，其中 k 和 c 是与输入字符串无关的常数，那么我们说这个问题可以在多项式时间内解决，并且我们把它放在 p 类中形式上，p 被定义为所有语言的集合，可以由一个确定性的多项式时间图灵机决定。也就是说，: mathbf { p } = { l: l = l (m) text { for some deterministic multipical time Turing machine } m }其中: l (m) = { w in Sigma ^ {

} : m text { accepes } w }和一个确定性多项式时间 Turing 机是一个满足以下两个条件的确定性 Turing 机 m:

M halts on all inputs w and
there exists [math]\displaystyle{ k \in N }[/math] such that [math]\displaystyle{ T_M(n)\in O(n^k) }[/math], where O refers to the big O notation and

[math]\displaystyle{ T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \} }[/math]

[math]\displaystyle{ t_M(w) = \text{ number of steps }M\text{ takes to halt on input }w. }[/math]

M halts on all inputs w and
there exists k \in N such that T_M(n)\in O(n^k), where O refers to the big O notation and

T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}

t_M(w) = \text{ number of steps }M\text{ takes to halt on input }w.

m 中止所有输入 w 和 # n 中存在 k，使得 t _ m (n)在 o (n ^ k)中，其中 o 指的是大 o 符号，并且: t _ m (n) = max { t _ m (w) : w 在 Sigma ^ {

} ，| w | = n } : t _ m (w) = text { number of steps } m text { takes to halt on input } w。

NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach to define NP is to use the concept of certificate and verifier. Formally, NP is defined as the set of languages over a finite alphabet that have a verifier that runs in polynomial time, where the notion of "verifier" is defined as follows.

NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach to define NP is to use the concept of certificate and verifier. Formally, NP is defined as the set of languages over a finite alphabet that have a verifier that runs in polynomial time, where the notion of "verifier" is defined as follows.

类似地，可以使用不确定图灵机(传统的方法)来定义 NP。然而，现代定义 NP 的方法是使用证书和验证者的概念。在形式上，NP 被定义为有限字母表上的一组语言，其中有一个验证者在多项式时间内运行，其中“验证者”的概念定义如下。

Let L be a language over a finite alphabet, Σ.

设 l 是有限字母表上的一种语言，σ。

L ∈ NP if, and only if, there exists a binary relation [math]\displaystyle{ R\subset\Sigma^{*}\times\Sigma^{*} }[/math] and a positive integer k such that the following two conditions are satisfied:

L ∈ NP if, and only if, there exists a binary relation R\subset\Sigma^{*}\times\Sigma^{*} and a positive integer k such that the following two conditions are satisfied:

L ∈ NP 当且仅当存在一个二元关系子集 r σ ^ { * }乘以 σ ^ { * }和一个正整数 k 使得满足以下两个条件:

For all x\in\Sigma^{*}, x\in L \Leftrightarrow\exists y\in\Sigma^{*} such that (x, y) ∈ R and |y|\in O(|x|^k); and
the language L_{R} = \{ x\# y:(x,y)\in R\} over \Sigma\cup\{\#\} is decidable by a deterministic Turing machine in polynomial time.

对于 Sigma ^ {

}中的所有 x，l 中的 x 在 Sigma ^ {
}中存在 y，使得(x，y)∈ r，| y | 在 o (| x | ^ k)中; 以及 | { x，y)在 σ 杯{ # }中的语言 l _ { r } = { x # y: (x，y)由多项式时间的确定性图灵机判定。

A Turing machine that decides L_R is called a verifier for L and a y such that (x, y) ∈ R is called a certificate of membership of x in L.

A Turing machine that decides LR is called a verifier for L and a y such that (x, y) ∈ R is called a certificate of membership of x in L.

一个决定 LR 的图灵机被称为 l 的验证器，y 使得(x，y)∈ r 被称为 l 中 x 的成员证书。

In general, a verifier does not have to be polynomial-time. However, for L to be in NP, there must be a verifier that runs in polynomial time.

一般来说，验证器不必是多项式时间的。然而，为了使 l 在 NP 中，必须有一个在多项式时间内运行的验证器。

Example

Let

[math]\displaystyle{ \mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ for integers } p, q \gt 1 \right \} }[/math]

[math]\displaystyle{ R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1\lt y \leq \sqrt x \text{ and } y \text{ divides } x \right \}. }[/math]

Clearly, the question of whether a given x is a composite is equivalent to the question of whether x is a member of COMPOSITE. It can be shown that COMPOSITE ∈ NP by verifying that it satisfies the above definition (if we identify natural numbers with their binary representations).

Let

\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ for integers } p, q > 1 \right \}

R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1<y \leq \sqrt x \text{ and } y \text{ divides } x \right \}.

Clearly, the question of whether a given x is a composite is equivalent to the question of whether x is a member of COMPOSITE. It can be shown that COMPOSITE ∈ NP by verifying that it satisfies the above definition (if we identify natural numbers with their binary representations).

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =.显然，给定的 x 是否为复合数的问题等价于 x 是否为 COMPOSITE 的成员的问题。证明了 COMPOSITE ∈ NP 满足上述定义(如果我们用它们的二进制表示来识别自然数)。

COMPOSITE also happens to be in P, a fact demonstrated by the invention of the AKS primality test.^[50]

COMPOSITE also happens to be in P, a fact demonstrated by the invention of the AKS primality test.

组合物碰巧也在 p 中，AKS质数测试的发明证明了这一点。

NP-completeness

There are many equivalent ways of describing NP-completeness.

有许多等价的方法来描述 np 完备性。

Let L be a language over a finite alphabet Σ.

设 l 是有限字母表 σ 上的一种语言。

L is NP-complete if, and only if, the following two conditions are satisfied:

当且仅当满足以下两个条件时，l 是 np- 完全的:

L ∈ NP; and
any L in NP is polynomial-time-reducible to L (written as [math]\displaystyle{ L' \leq_{p} L }[/math]), where [math]\displaystyle{ L' \leq_{p} L }[/math] if, and only if, the following two conditions are satisfied:
1. There exists f : Σ* → Σ* such that for all w in Σ* we have: [math]\displaystyle{ (w\in L' \Leftrightarrow f(w)\in L) }[/math]; and
2. there exists a polynomial-time Turing machine that halts with f(w) on its tape on any input w.

L ∈ NP; and
any L in NP is polynomial-time-reducible to L (written as L' \leq_{p} L), where L' \leq_{p} L if, and only if, the following two conditions are satisfied:
1. There exists f : Σ* → Σ* such that for all w in Σ* we have: (w\in L' \Leftrightarrow f(w)\in L); and
2. there exists a polynomial-time Turing machine that halts with f(w) on its tape on any input w.

l ∈ NP; 而且 NP 中的 # 任意 l 是多项式时间可约的 l (写为 l’leq _ { p } l) ，其中 l’leq _ { p } l 当且仅当满足以下两个条件: # 存在 f: σ

→ σ
，使得对于 σ
中的所有 w，我们有: (w 在 l’leftarrow f (w)中) ; # # 存在多项式时间图灵机，它在任意输入 w 的磁带上带 f (w)。

Alternatively, if L ∈ NP, and there is another NP-complete problem that can be polynomial-time reduced to L, then L is NP-complete. This is a common way of proving some new problem is NP-complete.

另外，如果 l ∈ NP，并且存在另一个 NP- 完全问题，可以将多项式时间约化为 l，那么 l 是 NP- 完全的。这是证明一些新问题是 np- 完全问题的常用方法。

形式化

形式化定义

P和NP

从概念上讲，判定问题是指从字母集合Σ中选出一些字符串w作为输入数据，根据这些输入数据判断输出“是”还是“否”。如果存在一种算法（如图灵机或无内存使用限制的电脑程序）对输入任意长度为n的字符串，在最多cn^k 个步骤内可以输出正确结果，其中k和c是与输入字符串无关的常数，那么我们称这个问题可以在多项式时间内求解，这类问题就称为P类问题。形式上，P定义为所有能被确定多项式时间图灵机判定的语言集合。也就是：

[math]\displaystyle{ \mathbf{P} = \{ L : L=L(M) M \text{ 是确定多项式时间图灵机 } \} }[/math]

其中

[math]\displaystyle{ L(M) = \{ w\in\Sigma^{*}: M \text{ 接受 } w \} }[/math]

确定多项式时间图灵机是一个满足以下两个条件的确定图灵机M：

对所有的输入w，M会停机
存在 [math]\displaystyle{ k \in N }[/math] 使得[math]\displaystyle{ T_{M}(n)\in O(n^{k}) }[/math]，其中O指大O表示法，并且
[math]\displaystyle{ T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \} }[/math]

[math]\displaystyle{ t_M(w) = \text{ 输入 }w \text{后 }M\text{ 停机需要的步骤数 }。 }[/math]

NP可以用类似非确定图灵机的方式（传统方式）定义。然而，现在定义NP主流的方法是用验证信息（certificate）与验证算法（verifier）的概念【备注：certificate和verifier是两个算法复杂度理论中两个专业术语，我难以翻译的非常满意，但我可以解释一下这两个词的意思，供你参考以更好的修改。我们考虑一个判定问题，某个数是否为偶数。certificate就是给出的待验证的信息，对于此问题可以是改数的分解因式。我们根据这些信息输入到算法中，判断这个数是否为偶数，这个算法就是verifier。更形式化的解释见此书，Computational Complexity: A Mordern Approach】。形式上，NP定义为用有限的字母表构建成的语言集合，这个字母表有一个多项式时间运行的验证算法，这个验证算法的步骤如下所示：

对于所有 [math]\displaystyle{ x\in\Sigma^{*} }[/math], [math]\displaystyle{ x\in L \Leftrightarrow\exists y\in\Sigma^{*} }[/math] 使得 (x, y) ∈ R 并且[math]\displaystyle{ |y|\in O(|x|^k) }[/math];
语言 [math]\displaystyle{ L_{R} = \{ x\# y:(x,y)\in R\} }[/math] 在[math]\displaystyle{ \Sigma\cup\{\#\} }[/math] 中对于确定图灵机来说是多项式时间可判定的。

判定L_R的图灵机称作对L的验证算法，使得 (x, y) ∈ R 的y称作L中对x的验证信息。

通常，验证算法不一定必须是多项式时间复杂度。但是对NP问题中的L来说，验证算法必须以多项式时间运行。

例子

令

[math]\displaystyle{ \mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ ，整数} p, q \gt 1 \right \} }[/math]

[math]\displaystyle{ R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1\lt y \leq \sqrt x \text{ 并且} y \text{ 整除} x \right \}. }[/math]

显然，x是否为合数这个问题等价于x是否在集合COMPOSITE中。通过验证其满足以上定义可以说明 COMPOSITE ∈ NP（如果我们用二进制表示自然数）【对于维基百科中括号里这句话的目的，并没有搞清楚】。

COMPOSITE恰巧也在P中，这个事实在AKS primality test中提到过。^[50]

NP完全

有许多相互等价的方式描述NP完全。

令L是有限字母集合Σ中的一种语言。

L是NP完全的当且仅当其满足以下两个条件：

L ∈ NP
任何在NP中的L可多项式时间归约为L（记作[math]\displaystyle{ L' \leq_{p} L }[/math]），其中[math]\displaystyle{ L' \leq_{p} L }[/math]，当且仅当满足以下两个条件：【无法理解这个逻辑】
1. 存在一个 f : Σ* → Σ* 使得对于所有在Σ*中的w，有[math]\displaystyle{ (w\in L' \Leftrightarrow f(w)\in L) }[/math]；并且
2. 存在一个多项式时间图灵机，它对于任何输入w以 f(w) 停机。【不清楚如何翻译解释f(w)，在链接中原句为there exists a polynomial-time Turing machine that halts with f(w) on its tape on any input w.】

另一种方法是，如果L ∈ NP，并且有另一个NP完全问题能在多项式时间内归约为L，那么L是NP完全问题。这是证明一个新问题是NP完全问题的常用方法。

Popular culture

The film Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the US government to solve the P versus NP problem.^[51]

The film Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the US government to solve the P versus NP problem.

这部由 Timothy Lanzone 导演的电影讲述了4位数学家受雇于美国政府解决货郎担 P/NP问题的故事。

In the sixth episode of The Simpsons模板:' seventh season "Treehouse of Horror VI", the equation P=NP is seen shortly after Homer accidentally stumbles into the "third dimension".^[52]^[53]

In the sixth episode of The Simpsons seventh season "Treehouse of Horror VI", the equation P=NP is seen shortly after Homer accidentally stumbles into the "third dimension".

在《辛普森一家》第七季第六集“恐怖树屋 VI”中，在荷马偶然跌入“第三维度”后不久，p = NP 方程式就出现了。

In the second episode of season 2 of Elementary, "Solve for X" revolves around Sherlock and Watson investigating the murders of mathematicians who were attempting to solve P versus NP.^[54]^[55]

In the second episode of season 2 of Elementary, "Solve for X" revolves around Sherlock and Watson investigating the murders of mathematicians who were attempting to solve P versus NP.

在《基本演绎法》第二季第二集中，“解决 x”围绕着夏洛克和华生调查那些试图解决 p 与 NP 的数学家的谋杀案展开。

影视元素

备注：popular culture 直译为大众文化,因以下所举内容皆为影视，而且此翻译我感觉并不地道，故修改的更加具体。

由蒂莫西·兰佐（Timothy Lanzone）执导的电影《旅行商》讲述了被美国政府雇佣的四个数学家解决P/NP问题的故事。^[51]

在《辛普森一家》第七季第六集“恐怖树屋 6”中，荷马（Homer）偶然跌入“第三维度”后，方程P=NP短暂出现。^[52]^[53]

在《基本演绎法》第二季第二集中，"求解x"围绕夏洛克和华生调查那些试图解决P/NP问题的数学家的谋杀案展开。^[54]^[55]

补充阅读

游戏复杂度 Game complexity
未被解决的数学问题 List of unsolved problems in mathematics
唯一游戏猜想 Unique games conjecture【过于专业，维基百科也解释的不太清楚，必须看定义，不然不知所云，可以参考该链接的2.4和2.5】
未被解决的计算机问题 Unsolved problems in computer science

Notes

↑ A nondeterministic Turing machine can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.
↑ Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of [math]\displaystyle{ O(N^2) }[/math] with a reasonable constant term would be disastrous. On the other hand, a solution that is [math]\displaystyle{ \Omega(N^4) }[/math] in almost all cases would not pose an immediate practical danger.

注解

↑ 非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。
↑ 算法对于加密方式的威胁有多大取决于这个算法有多高效。常数项不是非常大的[math]\displaystyle{ O(N^2) }[/math] 算法威胁非常大。如果大多数情况下算法复杂度是[math]\displaystyle{ \Omega(N^4) }[/math]，这并不会立刻带来实际性的威胁。

References

↑ ^1.0 ^1.1 Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF). Communications of the ACM. 52 (9): 78–86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. S2CID 5969255. Archived from the original (PDF) on 24 February 2011. Retrieved 26 January 2010.
↑ ^2.0 ^2.1 Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.
↑ ^3.0 ^3.1 Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. doi:10.1145/800157.805047. ISBN 9781450374644. http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047.
↑ ^4.0 ^4.1 L. A. Levin (1973). "Универсальные задачи перебора" (in русский). 9 (3) (Problems of Information Transmission ed.): 115–116. {{cite journal}}: Cite journal requires |journal= (help)
↑ ^5.0 ^5.1 NSA (2012). "Letters from John Nash" (PDF).
↑ ^6.0 ^6.1 Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.
↑ ^7.0 ^7.1 Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
↑ ^8.0 ^8.1 ^8.2 ^8.3 ^8.4 ^8.5 William I. Gasarch (June 2002). "The P=?NP poll" (PDF). SIGACT News. 33 (2): 34–47. CiteSeerX 10.1.1.172.1005. doi:10.1145/564585.564599. S2CID 36828694.
↑ ^9.0 ^9.1 William I. Gasarch. "The Second P=?NP poll" (PDF). SIGACT News. 74.
↑ ^10.0 ^10.1 ^10.2 ^10.3 "Guest Column: The Third P =? NP Poll1" (PDF). Retrieved 25 May 2020.
↑ ^11.0 ^11.1 Scott Aaronson. "PHYS771 Lecture 6: P, NP, and Friends". Retrieved 27 August 2007.
↑ ^12.0 ^12.1 "MSc course: Foundations of Computer Science". www.cs.ox.ac.uk. Retrieved 25 May 2020.
↑ ^13.0 ^13.1 Colbourn, Charles J. (1984). "The complexity of completing partial Latin squares". Discrete Applied Mathematics. 8 (1): 25–30. doi:10.1016/0166-218X(84)90075-1.
↑ ^14.0 ^14.1 I. Holyer (1981). "The NP-completeness of some edge-partition problems". SIAM J. Comput. 10 (4): 713–717. doi:10.1137/0210054.
↑ ^15.0 ^15.1 Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n × n chess requires time exponential in n". Journal of Combinatorial Theory, Series A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9.
↑ ^16.0 ^16.1 David Eppstein. "Computational Complexity of Games and Puzzles".
↑ ^17.0 ^17.1 Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41. Archived from the original on 15 September 2006. Retrieved 15 October 2017.
↑ ^18.0 ^18.1 Valiant, Leslie G. (1979). "The complexity of enumeration and reliability problems". SIAM Journal on Computing. 8 (3): 410–421. doi:10.1137/0208032.
↑ ^19.0 ^19.1 R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
↑ ^20.0 ^20.1 Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP". Information and Computation. 204 (5): 835–852. doi:10.1016/j.ic.2006.02.002.
↑ ^21.0 ^21.1 Schöning, Uwe (1988). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.
↑ ^22.0 ^22.1 Babai, László (2018). "Group, graphs, algorithms: the graph isomorphism problem". Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures. World Sci. Publ., Hackensack, NJ. pp. 3319–3336. MR 3966534.
↑ ^23.0 ^23.1 Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.
↑ Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
↑ ^25.0 ^25.1 Kawarabayashi, K. I.; Kobayashi, Y.; Reed, B. (2012). "The disjoint paths problem in quadratic time". Journal of Combinatorial Theory, Series B. 102 (2): 424–435. doi:10.1016/j.jctb.2011.07.004.
↑ ^26.0 ^26.1 Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303. CiteSeerX 10.1.1.114.3864. doi:10.1016/0196-6774(87)90043-5.
↑ ^27.0 ^27.1 Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley. Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. 4. New York: Oxford University Press. pp. 103–144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky. http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps.
↑ ^28.0 ^28.1 Cook, Stephen (April 2000). "The P versus NP Problem" (PDF). Clay Mathematics Institute. Retrieved 18 October 2006.
↑ Rosenberger, Jack (May 2012). "P vs. NP poll results". Communications of the ACM. 55 (5): 10.
↑ Scott Aaronson. "Reasons to believe"., point 9.
↑ ^31.0 ^31.1 See Horie, S.; Watanabe, O. (1997). "Hard instance generation for SAT". Algorithms and Computation. Lecture Notes in Computer Science. 1350. Springer. pp. 22–31. arXiv:cs/9809117. Bibcode 1998cs........9117H. doi:10.1007/3-540-63890-3_4. ISBN 978-3-540-63890-2. for a reduction of factoring to SAT. A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.
↑ ^32.0 ^32.1 See, for example, Massacci, F. & Marraro, L. (2000). "Logical cryptanalysis as a SAT problem". Journal of Automated Reasoning. 24 (1): 165–203. CiteSeerX 10.1.1.104.962. doi:10.1023/A:1006326723002. S2CID 3114247. in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.
↑ ^33.0 ^33.1 De, Debapratim; Kumarasubramanian, Abishek; Venkatesan, Ramarathnam (2007). "Inversion attacks on secure hash functions using SAT solvers". Theory and Applications of Satisfiability Testing--SAT 2007. International Conference on Theory and Applications of Satisfiability Testing. Springer. pp. 377–382. doi:10.1007/978-3-540-72788-0_36.
↑ ^34.0 ^34.1 Berger B, Leighton T (1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete". J. Comput. Biol. 5 (1): 27–40. CiteSeerX 10.1.1.139.5547. doi:10.1089/cmb.1998.5.27. PMID 9541869.
↑ History of this letter and its translation from Michael Sipser. "The History and Status of the P versus NP question" (PDF).
↑ David S. Johnson (2012). "A Brief History of NP-Completeness, 1954–2012". CiteSeerX 10.1.1.399.1480. From pages 359–376 of Optimization Stories, M. Grötschel (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.
↑ Knuth, Donald E. (20 May 2014). Twenty Questions for Donald Knuth. informit.com. InformIT. Retrieved 20 July 2014.
↑ L. R. Foulds (October 1983). "The Heuristic Problem-Solving Approach". Journal of the Operational Research Society. 34 (10): 927–934. doi:10.2307/2580891. JSTOR 2580891.
↑ R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995
↑ "Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"". Archived from the original on 15 November 2013.
↑ ^41.0 ^41.1 T. P. Baker; J. Gill; R. Solovay. (1975). "Relativizations of the P =? NP Question". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.
↑ ^42.0 ^42.1 Razborov, Alexander A.; Steven Rudich (1997). "Natural proofs". Journal of Computer and System Sciences. 55 (1): 24–35. doi:10.1006/jcss.1997.1494.
↑ ^43.0 ^43.1 S. Aaronson & A. Wigderson (2008). Algebrization: A New Barrier in Complexity Theory (PDF). Proceedings of ACM STOC'2008. pp. 731–740. doi:10.1145/1374376.1374481.
↑ ^44.0 ^44.1 Aaronson, Scott. "Is P Versus NP Formally Independent?" (PDF)..
↑ ^45.0 ^45.1 Ben-David, Shai; Halevi, Shai (1992). "On the independence of P versus NP". Technical Report. 714. Technion. {{cite journal}}: Cite journal requires |journal= (help).
↑ ^46.0 ^46.1 John Markoff (8 October 2009). "Prizes Aside, the P-NP Puzzler Has Consequences". The New York Times.
↑ ^47.0 ^47.1 Gerhard J. Woeginger. "The P-versus-NP page". Retrieved 24 June 2018.
↑ ^48.0 ^48.1 Markoff, John (16 August 2010). "Step 1: Post Elusive Proof. Step 2: Watch Fireworks". The New York Times. Retrieved 20 September 2010.
↑ ^49.0 ^49.1 Elvira Mayordomo. "P versus NP" -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-的存檔，存档日期16 February 2012. Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).
↑ ^50.0 ^50.1 Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.
↑ ^51.0 ^51.1 Geere, Duncan (26 April 2012). "'Travelling Salesman' movie considers the repercussions if P equals NP". Wired UK. Retrieved 26 April 2012.
↑ ^52.0 ^52.1 Hardesty, Larry. "Explained: P vs. NP".
↑ ^53.0 ^53.1 Shadia, Ajam. "What is the P vs. NP problem? Why is it important?".
↑ ^54.0 ^54.1 Gasarch, William (7 October 2013). "P vs NP is Elementary? No— P vs NP is ON Elementary". blog.computationalcomplexity.org (in English). Retrieved 6 July 2018.
↑ ^55.0 ^55.1 Kirkpatrick, Noel (4 October 2013). "Elementary Solve for X Review: Sines of Murder". TV.com. Retrieved 6 July 2018.

Sources

Rachel Crowell (28 May 2021). "The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved". www.scientificamerican.com. Retrieved 21 June 2021. This problem concerns the issue of whether questions that are easy to verify (a class of queries called NP) also have solutions that are easy to find (a class called P).
Hosch, William L (11 August 2009). "P versus NP problem mathematics". www.britannica.com (March 15, 2012 Gregersen, Smith; revised, updated). Indiana University Northwest (blogs.britannica.com/author/whosch/page/3/). Retrieved 20 June 2021.{{cite encyclopedia}}: CS1 maint: location (link)
"P vs NP Problem". www.claymath.org (Cook, Levin). Retrieved 20 June 2021. Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem...

External links

模板:Sister project links

Fortnow, L.; Gasarch, W. "Computational complexity".
Aviad Rubinstein's Hardness of Approximation Between P and NP, winner of the ACM's 2017 Doctoral Dissertation Award.
"P vs. NP and the Computational Complexity Zoo". 26 August 2014. Archived from the original on 24 November 2021 – via YouTube.模板:Cbignore

模板:ComplexityClasses

Category:1956 in computing Category:Computer-related introductions in 1956 Category:Conjectures Category:Mathematical optimization Category:Millennium Prize Problems Category:Structural complexity theory Category:Unsolved problems in computer science Category:Unsolved problems in mathematics

类别: 1956计算机范畴: 1956年与计算机有关的介绍类别: 猜测范畴: 最优化范畴: 千禧年大奖难题范畴: 结构复杂性理论范畴: 计算机科学中未解决的问题范畴: 数学中未解决的问题

This page was moved from wikipedia:en:P versus NP problem. Its edit history can be viewed at P/NP问题/edithistory

[1] A nondeterministic Turing machine can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.

[33] Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of [math]\displaystyle{ O(N^2) }[/math] with a reasonable constant term would be disastrous. On the other hand, a solution that is [math]\displaystyle{ \Omega(N^4) }[/math] in almost all cases would not pose an immediate practical danger.

[4] 非确定图灵机状态转移时可以不由前一状态决定。这种机器（碰巧）进入有正确答案的状态，然后按部就班进行验证，通过这种方式它可以在多项式时间内求解NP问题。但这种机器并不适用于解决实际问题，不过可以用作理论模型。

[38] 算法对于加密方式的威胁有多大取决于这个算法有多高效。常数项不是非常大的[math]\displaystyle{ O(N^2) }[/math] 算法威胁非常大。如果大多数情况下算法复杂度是[math]\displaystyle{ \Omega(N^4) }[/math]，这并不会立刻带来实际性的威胁。

[:5-2] 1.0 ^1.1 Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF). Communications of the ACM. 52 (9): 78–86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. S2CID 5969255. Archived from the original (PDF) on 24 February 2011. Retrieved 26 January 2010.

[:6-3] 2.0 ^2.1 Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.

[:7-5] 3.0 ^3.1 Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. doi:10.1145/800157.805047. ISBN 9781450374644. http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047.

[:8-6] 4.0 ^4.1 L. A. Levin (1973). "Универсальные задачи перебора" (in русский). 9 (3) (Problems of Information Transmission ed.): 115–116. {{cite journal}}: Cite journal requires |journal= (help)

[:9-7] 5.0 ^5.1 NSA (2012). "Letters from John Nash" (PDF).

[:10-8] 6.0 ^6.1 Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.

[:11-9] 7.0 ^7.1 Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.

[poll-10] 8.0 ^8.1 ^8.2 ^8.3 ^8.4 ^8.5 William I. Gasarch (June 2002). "The P=?NP poll" (PDF). SIGACT News. 33 (2): 34–47. CiteSeerX 10.1.1.172.1005. doi:10.1145/564585.564599. S2CID 36828694.

[poll2-11] 9.0 ^9.1 William I. Gasarch. "The Second P=?NP poll" (PDF). SIGACT News. 74.

[poll3-12] 10.0 ^10.1 ^10.2 ^10.3 "Guest Column: The Third P =? NP Poll1" (PDF). Retrieved 25 May 2020.

[Scott-13] 11.0 ^11.1 Scott Aaronson. "PHYS771 Lecture 6: P, NP, and Friends". Retrieved 27 August 2007.

[:12-14] 12.0 ^12.1 "MSc course: Foundations of Computer Science". www.cs.ox.ac.uk. Retrieved 25 May 2020.

[:13-15] 13.0 ^13.1 Colbourn, Charles J. (1984). "The complexity of completing partial Latin squares". Discrete Applied Mathematics. 8 (1): 25–30. doi:10.1016/0166-218X(84)90075-1.

[:14-16] 14.0 ^14.1 I. Holyer (1981). "The NP-completeness of some edge-partition problems". SIAM J. Comput. 10 (4): 713–717. doi:10.1137/0210054.

[Fraenkel1981-17] 15.0 ^15.1 Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n × n chess requires time exponential in n". Journal of Combinatorial Theory, Series A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9.

[:15-18] 16.0 ^16.1 David Eppstein. "Computational Complexity of Games and Puzzles".

[:16-19] 17.0 ^17.1 Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41. Archived from the original on 15 September 2006. Retrieved 15 October 2017.

[:17-20] 18.0 ^18.1 Valiant, Leslie G. (1979). "The complexity of enumeration and reliability problems". SIAM Journal on Computing. 8 (3): 410–421. doi:10.1137/0208032.

[:18-21] 19.0 ^19.1 R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.

[AK06-22] 20.0 ^20.1 Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP". Information and Computation. 204 (5): 835–852. doi:10.1016/j.ic.2006.02.002.

[:19-23] 21.0 ^21.1 Schöning, Uwe (1988). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.

[:20-24] 22.0 ^22.1 Babai, László (2018). "Group, graphs, algorithms: the graph isomorphism problem". Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures. World Sci. Publ., Hackensack, NJ. pp. 3319–3336. MR 3966534.

[:21-25] 23.0 ^23.1 Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.

[Pisinger2003-26] Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark

[kkr12-27] 25.0 ^25.1 Kawarabayashi, K. I.; Kobayashi, Y.; Reed, B. (2012). "The disjoint paths problem in quadratic time". Journal of Combinatorial Theory, Series B. 102 (2): 424–435. doi:10.1016/j.jctb.2011.07.004.

[:22-28] 26.0 ^26.1 Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303. CiteSeerX 10.1.1.114.3864. doi:10.1016/0196-6774(87)90043-5.

[:23-29] 27.0 ^27.1 Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley. Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. 4. New York: Oxford University Press. pp. 103–144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky. http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps.

[:35-30] 28.0 ^28.1 Cook, Stephen (April 2000). "The P versus NP Problem" (PDF). Clay Mathematics Institute. Retrieved 18 October 2006.

[31] Rosenberger, Jack (May 2012). "P vs. NP poll results". Communications of the ACM. 55 (5): 10.

[32] Scott Aaronson. "Reasons to believe"., point 9.

[:25-34] 31.0 ^31.1 See Horie, S.; Watanabe, O. (1997). "Hard instance generation for SAT". Algorithms and Computation. Lecture Notes in Computer Science. 1350. Springer. pp. 22–31. arXiv:cs/9809117. Bibcode 1998cs........9117H. doi:10.1007/3-540-63890-3_4. ISBN 978-3-540-63890-2. for a reduction of factoring to SAT. A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.

[:26-35] 32.0 ^32.1 See, for example, Massacci, F. & Marraro, L. (2000). "Logical cryptanalysis as a SAT problem". Journal of Automated Reasoning. 24 (1): 165–203. CiteSeerX 10.1.1.104.962. doi:10.1023/A:1006326723002. S2CID 3114247. in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.

[:27-36] 33.0 ^33.1 De, Debapratim; Kumarasubramanian, Abishek; Venkatesan, Ramarathnam (2007). "Inversion attacks on secure hash functions using SAT solvers". Theory and Applications of Satisfiability Testing--SAT 2007. International Conference on Theory and Applications of Satisfiability Testing. Springer. pp. 377–382. doi:10.1007/978-3-540-72788-0_36.

[Berger-37] 34.0 ^34.1 Berger B, Leighton T (1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete". J. Comput. Biol. 5 (1): 27–40. CiteSeerX 10.1.1.139.5547. doi:10.1089/cmb.1998.5.27. PMID 9541869.

[39] History of this letter and its translation from Michael Sipser. "The History and Status of the P versus NP question" (PDF).

[40] David S. Johnson (2012). "A Brief History of NP-Completeness, 1954–2012". CiteSeerX 10.1.1.399.1480. From pages 359–376 of Optimization Stories, M. Grötschel (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.

[41] Knuth, Donald E. (20 May 2014). Twenty Questions for Donald Knuth. informit.com. InformIT. Retrieved 20 July 2014.

[:29-42] L. R. Foulds (October 1983). "The Heuristic Problem-Solving Approach". Journal of the Operational Research Society. 34 (10): 927–934. doi:10.2307/2580891. JSTOR 2580891.

[:30-43] R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995

[:31-44] "Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"". Archived from the original on 15 November 2013.

[:32-45] 41.0 ^41.1 T. P. Baker; J. Gill; R. Solovay. (1975). "Relativizations of the P =? NP Question". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.

[:33-46] 42.0 ^42.1 Razborov, Alexander A.; Steven Rudich (1997). "Natural proofs". Journal of Computer and System Sciences. 55 (1): 24–35. doi:10.1006/jcss.1997.1494.

[:34-47] 43.0 ^43.1 S. Aaronson & A. Wigderson (2008). Algebrization: A New Barrier in Complexity Theory (PDF). Proceedings of ACM STOC'2008. pp. 731–740. doi:10.1145/1374376.1374481.

[:36-48] 44.0 ^44.1 Aaronson, Scott. "Is P Versus NP Formally Independent?" (PDF)..

[:37-49] 45.0 ^45.1 Ben-David, Shai; Halevi, Shai (1992). "On the independence of P versus NP". Technical Report. 714. Technion. {{cite journal}}: Cite journal requires |journal= (help).

[:24-50] 46.0 ^46.1 John Markoff (8 October 2009). "Prizes Aside, the P-NP Puzzler Has Consequences". The New York Times.

[:28-51] 47.0 ^47.1 Gerhard J. Woeginger. "The P-versus-NP page". Retrieved 24 June 2018.

[NYT2010-52] 48.0 ^48.1 Markoff, John (16 August 2010). "Step 1: Post Elusive Proof. Step 2: Watch Fireworks". The New York Times. Retrieved 20 September 2010.

[:38-53] 49.0 ^49.1 Elvira Mayordomo. "P versus NP" -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-的存檔，存档日期16 February 2012. Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).

[Agrawal-54] 50.0 ^50.1 Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.

[:0-55] 51.0 ^51.1 Geere, Duncan (26 April 2012). "'Travelling Salesman' movie considers the repercussions if P equals NP". Wired UK. Retrieved 26 April 2012.

[:1-56] 52.0 ^52.1 Hardesty, Larry. "Explained: P vs. NP".

[:2-57] 53.0 ^53.1 Shadia, Ajam. "What is the P vs. NP problem? Why is it important?".

[:3-58] 54.0 ^54.1 Gasarch, William (7 October 2013). "P vs NP is Elementary? No— P vs NP is ON Elementary". blog.computationalcomplexity.org (in English). Retrieved 6 July 2018.

[:4-59] 55.0 ^55.1 Kirkpatrick, Noel (4 October 2013). "Elementary Solve for X Review: Sines of Murder". TV.com. Retrieved 6 July 2018.

[Note 1]

[1]

[2]

[注 1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[Note 2]

[31]

[32]

[33]

[34]

[注 2]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

P/NP问题

Example

例子

History

历史

Context

背景

NP-completeness

NP完全性

Harder problems

更难的问题

Problems in NP not known to be in P or NP-complete

不知道属于P还是NP完全的NP问题

Does P mean "easy"?

P意味着“容易”？

Reasons to believe P ≠ NP or P = NP

认为P ≠ NP 或 P = NP的原因

Consequences of solution

P = NP

P ≠ NP

不同结论的影响

P = NP

P ≠ NP

Results about difficulty of proof

关于证明难度的结果

Claimed solutions

声称的解答

Logical characterizations

逻辑特征【过多逻辑学的专业词汇，我许多句子看不懂，编辑需要重点关注】

Polynomial-time algorithms

多项式时间算法

Formal definitions

P and NP

Example

NP-completeness

形式化定义

P和NP

例子

NP完全

Popular culture

影视元素

See also

补充阅读

Notes

注解

References

Sources

Further reading

External links

导航菜单

搜索