更改

P/NP问题 (查看源代码)

2022年3月21日 (一) 15:05的版本

添加609字节、 2022年3月21日 (一) 15:05

小

→‎NP完全性：测试源代码编辑数学公式

第9行：第9行：

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

−

~~【问题】：部分参考文献爬取下来存在格式问题，图片没爬取下来~~

+

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

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

第60行：第60行：

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

−

== Example==

+

==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-complete]]ness. 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.

第98行：第98行：

In this theory, the class P consists of all those ''[https://wiki.swarma.org/index.php/Decision_problem decision problem]s'' (defined [https://wiki.swarma.org/index.php/P/NP%E9%97%AE%E9%A2%98#Formal_definitions below]) that can be solved on a deterministic sequential machine in an amount of time that is [https://wiki.swarma.org/index.php/Polynomial polynomial] in the size of the input; the class [https://wiki.swarma.org/index.php/NP_(complexity) NP] consists of all those decision problems whose positive solutions can be verified in [https://wiki.swarma.org/index.php/Polynomial_time polynomial time] given the right information, or equivalently, whose solution can be found in polynomial time on a [https://wiki.swarma.org/index.php/Non-deterministic_Turing_machine non-deterministic] machine.<ref name=":11">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.</ref> Clearly, P ⊆ NP. Arguably, the biggest open question in [https://wiki.swarma.org/index.php/Theoretical_computer_science 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? 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类问题吗？

第144行：第144行：

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

−

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

+

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

==Harder problems==

−

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 [[big O notation|O]](2''p''(''n'')) time, where ''p''(''n'') is a polynomial function of ''n''. A decision problem is [[EXPTIME#EXPTIME-complete|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<ref name="Fraenkel1981">{{Cite journal| author = [[Aviezri Fraenkel]] and D. Lichtenstein| title = Computing a perfect strategy for ''n'' × ''n'' chess requires time exponential in ''n''| journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series A]]| volume = 31| issue = 2| year = 1981| pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9| doi-access = free}}</ref> and similar problems for other board games.<ref>{{Cite web|title=Computational Complexity of Games and Puzzles |url=http://www.ics.uci.edu/~eppstein/cgt/hard.html |author=[[David Eppstein]]}}</ref>

+

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 [[big O notation|O]](2''p''(''n'')) time, where ''p''(''n'') is a polynomial function of ''n''. A decision problem is [[EXPTIME#EXPTIME-complete|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<ref name="Fraenkel1981">{{Cite journal| author = [[Aviezri Fraenkel]] and D. Lichtenstein| title = Computing a perfect strategy for ''n'' × ''n'' chess requires time exponential in ''n''| journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series A]]| volume = 31| issue = 2| year = 1981| pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9| doi-access = free}}</ref> and similar problems for other board games.<ref name=":15">{{Cite web|title=Computational Complexity of Games and Puzzles |url=http://www.ics.uci.edu/~eppstein/cgt/hard.html |author=[[David Eppstein]]}}</ref>

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.

第168行：第168行：

==更难的问题==

−

虽然不知道P=NP是否成立，但P之外的问题是已知的。正如P类是根据多项式运行时间定义的，EXPTIME类是所有具有指数运行时间的决策问题的集合。换句话说，EXPTIME中的任何问题都可以通过O(2p(n))~~时间内的确定性图灵机来解决，其中p~~(n)是n的多项式函数。如果决策问题在EXPTIME中，则它是EXPTIME完备的，并且EXPTIME中的每个问题都有一个多项式时间，并且对它进行了多次归约。许多问题已知是一次性完成的。因为可以证明P≠ EXPTIME，这些问题在P之外，因此需要的时间超过多项式时间。实际上，根据时间层次定理，它们不能在明显少于指数时间的情况下求解。例如，在N×N棋盘上的国际象棋找到一个下棋的完美策略，以及其他棋盘游戏一样的类似问题。

+

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

−

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

+

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

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

第232行：第232行：

这个问题目前最好的量子算法——Shor算法，是多项式时间算法。但这并不能说明非量子复杂度类别的问题所在。

−

==Does P mean "easy"?==

+

==Does P mean "easy"? ==

[[File:KnapsackEmpComplexity.GIF|thumb|310 px|The graph shows the running time vs. problem size for a [[knapsack problem]] of a state-of-the-art, specialized algorithm. The [[Curve fitting|quadratic fit]] suggests that the algorithmic complexity of the problem is O((log(''n''))2).<ref name="Pisinger2003">Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark</ref>|链接=Special:FilePath/KnapsackEmpComplexity.GIF]]

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|reason=Accurate in what way, according to whom?|date=January 2021}} assumption in complexity theory; however, it has some caveats.

第315行：第315行：

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

−

===P = NP===

+

=== 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.

第346行：第346行：

*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.

+

*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.

第352行：第352行：

*现有的实现的公开密钥加密，请看一个因数化为 SAT。一个512位因式分解问题(因式分解后为8400mips 年)转化为一个由63,652个变量和406,860个子句组成的 SAT 问题。是许多现代安全应用的基础，例如通过互联网进行安全的金融交易。

*对称密码，例如 AES 或3des---- 例如，将 DES 的一个实例编码为具有10336个变量和61935个子句的 SAT 问题。一个3des 问题实例大约是这个大小的3倍。用来加密通讯数据。

−

*加密哈希，是区块链加密货币(如比特币)的基础，用于验证软件更新。对于这些应用程序，要找到一个散列到给定值的预映像一定很困难，而且理想情况下应该需要 EXPTIME。然而，如果 p = NP，则可以在多项式时间内找到一个前图像 m，通过简化到 SAT。这些将需要修改或取代的信息-理论上安全的解决方案不固有地基于 P-NP 不对等。

+

* 加密哈希，是区块链加密货币(如比特币)的基础，用于验证软件更新。对于这些应用程序，要找到一个散列到给定值的预映像一定很困难，而且理想情况下应该需要 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;<ref name="Berger">{{Cite journal|author=[[Bonnie Berger|Berger B]], [[F. Thomson Leighton|Leighton T]] |title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete |journal=J. Comput. Biol. |volume=5 |issue=1 |pages=27–40 |year=1998 |pmid=9541869 |doi=10.1089/cmb.1998.5.27 |citeseerx=10.1.1.139.5547 }}</ref> if these problems were efficiently solvable, it could spur considerable advances in life sciences and biotechnology.

第429行：第429行：

Donald Knuth表示，他已经开始相信P=NP，但对可能的证明结果所带来的影响持保留态度：<blockquote>[...] 如果你想象一个有限但非常大的数字M，比如说10↑↑↑↑3，这在我的论文“应对有限性”中讨论过。然后有大量可能的算法对n个给定的比特进行nM位、加法或移位运算，很难相信所有这些算法都失败了。然而，我的主要观点是，我不相信等式P=NP会有帮助，即使它被证明了，因为这样的证明几乎肯定是没有贡献的。</blockquote>

−

===P ≠ NP===

+

===P ≠ NP ===

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

第444行：第444行：

{| class="wikitable"

|-

−

! Classification

+

!Classification

!Definition

|-

第460行：第460行：

{| class="wikitable"

|-

−

!Classification

+

! 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.

+

| 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

+

| 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.

|-

第519行：第519行：

虽然P对NP问题通常被认为是未解决的，许多业余和一些专业研究人员已经提出了解决方案。Gerhard J.Woeginger保持着一份列表，截至2016年，该列表包含62个据称是P=NP的证明，50个P的证明≠ NP，2个证明问题是不可判定的，1个证明问题是不可判定的。一些试图解决P对NP的尝试得到了媒体的短暂关注，尽管这些尝试后来遭到了驳斥。

−

== Logical characterizations==

+

==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]].

第545行：第545行：

类似地，NP是一组可在存在二阶逻辑中表达的语言，也就是二阶逻辑，被限制为排除关系、函数和子集上的通用量化。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，问题“P是NP的适当子集”可以重新表述为“存在二阶逻辑能够描述（具有非平凡特征的有限线性有序结构的）语言，而具有最小不动点的一阶逻辑不能吗？”。甚至可以从前面的描述中删除“存在”一词，因为P=NP当且仅当P=PH（因为前者将确定NP=co-NP，这反过来意味着NP=PH）。

−

==Polynomial-time algorithms==

+

==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 [[Leonid Levin|Levin]] (without any citation), is such an example below. It correctly accepts the NP-complete language [[subset sum problem|SUBSET-SUM]]. It runs in polynomial time on inputs that are in SUBSET-SUM if and only if P = NP:

第645行：第645行：

==Formal definitions==

−

===P and NP===

+

===P and NP ===

Conceptually speaking, a ''decision problem'' is a problem that takes as input some [[String (computer science)|string]] ''w'' over an alphabet Σ, and outputs "yes" or "no". If there is an [[algorithm]] (say a [[Turing machine]], or a [[Computer programming|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,

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

第659行：第659行：

= = = 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 text { accepes } w }和一个确定性多项式时间 Turing 机是一个满足以下两个条件的确定性 Turing 机 m:

#''M'' halts on all inputs ''w'' and

第667行：第667行：

#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

+

#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.

+

:: 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 ^ {

+

#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。

第693行：第693行：

#<abbr title="For all strings x in Σ*, x is in L if and only if there is a y in Σ* such that (x, y) is in R and the length of y is polynomial in the length of x">For all <math>x\in\Sigma^{*}</math>, <math>x\in L \Leftrightarrow\exists y\in\Sigma^{*}</math> such that (''x'', ''y'') ∈ ''R'' and <math>|y|\in O(|x|^k)</math></abbr>; and

−

# the language <abbr title="L[R], consisting of x followed by y with a delimiter in the middle"><math>L_{R} = \{ x\# y:(x,y)\in R\}</math> over <math>\Sigma\cup\{\#\}</math></abbr> is decidable by a deterministic Turing machine in polynomial time.

+

#the language <abbr title="L[R], consisting of x followed by y with a delimiter in the middle"><math>L_{R} = \{ x\# y:(x,y)\in R\}</math> over <math>\Sigma\cup\{\#\}</math></abbr> is decidable by a deterministic Turing machine in polynomial time.

−

#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

+

# 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)由多项式时间的确定性图灵机判定。

+

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

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''.

第714行：第714行：

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

−

==== Example====

+

====Example====

Let

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

第733行：第733行：

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

−

===NP-completeness===

+

=== NP-completeness===

第757行：第757行：

#any ''L'' in NP is polynomial-time-reducible to ''L'' (written as <math>L' \leq_{p} L</math>), where <math>L' \leq_{p} L</math> if, and only if, the following two conditions are satisfied:

## There exists ''f'' : Σ* → Σ* such that for all ''w'' in Σ* we have: <math>(w\in L' \Leftrightarrow f(w)\in L)</math>; and

−

##there exists a polynomial-time Turing machine that halts with ''f''(''w'') on its tape on any input ''w''.

+

## 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:

##There exists f : Σ* → Σ* such that for all w in Σ* we have: (w\in L' \Leftrightarrow f(w)\in L); and

−

## there exists a polynomial-time Turing machine that halts with f(w) on its tape on any input 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 (写为 l’leq _ { p } l) ，其中 l’leq _ { p } l 当且仅当满足以下两个条件: # 存在 f: σ

*→ σ

*，使得对于 σ

−

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

+

* 中的所有 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.

第787行：第787行：

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

−

# 对所有的输入''w''，''M''会停机

+

#对所有的输入''w''，''M''会停机

#存在 $k \in N $ 使得 $T_{M}(n)\in O(n^{k})$，其中''O''指大O表示法，

#:<math>T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}</math>

第801行：第801行：

通常，验证算法不一定必须是多项式时间复杂度。但是对NP类问题中的''L''来说，必须能够在多项式时间内得到验证。【直译：验证算法必须以多项式时间运行】

−

==== 例子 ====

+

====例子====

令

第819行：第819行：

#''L'' ∈ NP

−

#any ''L'' in NP is polynomial-time-reducible to ''L'' (written as ), where if, and only if, the following two conditions are satisfied:

+

# any ''L'' in NP is polynomial-time-reducible to ''L'' (written as ), where if, and only if, the following two conditions are satisfied:

−

## There exists ''f'' : Σ* → Σ* such that for all ''w'' in Σ* we have: ; and

+

##There exists ''f'' : Σ* → Σ* such that for all ''w'' in Σ* we have: ; and

−

##there exists a polynomial-time Turing machine that halts with ''f''(''w'') on its tape on any input ''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完全问题的常用方法。

第844行：第844行：

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

−

==影视元素==

+

==影视元素 ==

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

第871行：第871行：

*[[wikipedia:Unsolved_problems_in_computer_science|未被解决的计算机问题 Unsolved problems in computer science]]

−

== Notes==

+

==Notes==

−

==注解 ==

+

==注解==

−

==References==

+

==References ==

Haojie

134

个编辑

更改

P/NP问题 (查看源代码)

2022年3月21日 (一) 15:05的版本

导航菜单

搜索