更改

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

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

删除164字节、 2022年3月21日 (一) 15:15

无编辑摘要

第170行：第170行：

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

+

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

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

−

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

+

== Problems in NP not known to be in P or 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.<ref>R. E. Ladner "On the structure of polynomial time reducibility," ''[[wikipedia:Journal_of_the_ACM|Journal of the ACM]]'' 22, pp. 151–171, 1975. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].</ref>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.

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

第268行：第268行：

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

−

==Reasons to believe P ≠ NP or 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 ''?''.<ref name="Official Problem Description" /> According to polls,<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref><ref>{{cite journal|title=P vs. NP poll results|journal=Communications of the ACM|date=May 2012|volume=55|issue=5|page=10|first=Jack|last=Rosenberger|url=http://mags.acm.org/communications/201205?pg=12}}</ref> 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 (complexity)|PH]].

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

第329行：第329行：

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<ref group="Note">Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of <math>O(N^2)</math> with a reasonable constant term would be disastrous. On the other hand, a solution that is <math>\Omega(N^4)</math> in almost all cases would not pose an immediate practical danger.</ref> to an NP-complete problem such as [[Boolean satisfiability problem#3-satisfiability|3-SAT]] would break most existing cryptosystems including:

−

*Existing implementations of [[public-key cryptography]],<ref>See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997

+

* Existing implementations of [[public-key cryptography]],<ref>See {{cite book |contribution=Hard instance generation for SAT |author1=Horie, S. |author2=Watanabe, O. |title=Algorithms and Computation |pages=22–31 |year=1997

|publisher=Springer |arxiv=cs/9809117 |bibcode=1998cs........9117H |doi=10.1007/3-540-63890-3_4 |series=Lecture Notes in Computer Science |isbn=978-3-540-63890-2 |volume=1350}} 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.</ref> a foundation for many modern security applications such as secure financial transactions over the Internet.

*[[Symmetric cipher]]s such as [[Advanced Encryption Standard|AES]] or [[Triple DES|3DES]],<ref>See, for example, {{cite journal |title=Logical cryptanalysis as a SAT problem |author1=Massacci, F. |author2=Marraro, L. |name-list-style=amp |journal=Journal of Automated Reasoning |volume=24 |issue=1 |pages=165–203 |year=2000 |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.</ref> used for the encryption of communications data.

第344行：第344行：

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.

+

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

第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，已经大部分聚焦于这种研究。

第451行：第451行：

|-

|[[Natural proof]]s

−

|In 1993, [[Alexander Razborov]] and [[Steven Rudich]] defined a general class of proof techniques for circuit complexity lower bounds, called ''[[natural proof]]s''.<ref>{{cite journal |author1=Razborov, Alexander A. |author2=Steven Rudich |title=Natural proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |year=1997 |pages=24–35 |doi=10.1006/jcss.1997.1494|doi-access=free }}</ref> 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.

+

| In 1993, [[Alexander Razborov]] and [[Steven Rudich]] defined a general class of proof techniques for circuit complexity lower bounds, called ''[[natural proof]]s''.<ref>{{cite journal |author1=Razborov, Alexander A. |author2=Steven Rudich |title=Natural proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |year=1997 |pages=24–35 |doi=10.1006/jcss.1997.1494|doi-access=free }}</ref> 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

第460行：第460行：

{| class="wikitable"

|-

−

! Classification

+

!Classification

!Definition

|-

第467行：第467行：

|-

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

+

| 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

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

第644行：第644行：

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

−

==Formal definitions==

+

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

第668行：第668行：

#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(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 ^ {

−

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

+

* } ，| 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 (complexity)|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.

第700行：第700行：

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

第733行：第733行：

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

−

=== NP-completeness===

+

===NP-completeness===

第756行：第756行：

#''L'' ∈ NP; and

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

+

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

第767行：第767行：

*→ σ

*，使得对于 σ

−

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

第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 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 直译为大众文化,因以下所举内容皆为影视，而且此翻译我感觉并不地道，故修改的更加具体。

第862行：第862行：

*List of unsolved problems in mathematics

*Unique games conjecture

−

*Unsolved problems in computer science

+

* Unsolved problems in computer science

==补充阅读==

第877行：第877行：

−

==References ==

+

==References==

第927行：第927行：

*

−

==External links==

+

== External links==

{{Sister project links| wikt=no | commons=no | b=no | n=no | q=P versus NP problem | s=no | v=no | voy=no | species=no | d=no}}

Haojie

134

个编辑

更改

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

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

导航菜单

搜索