更改

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

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

{{Main article|NP-intermediate|l1=NP-intermediate}}

{{Main article|NP-intermediate|l1=NP-intermediate}}

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.

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 name=":18">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.

  | doi = 10.1016/j.ic.2006.02.002

  | doi = 10.1016/j.ic.2006.02.002

  | doi-access = free

  | doi-access = free

  }}</ref> If graph isomorphism is NP-complete, the [[polynomial time hierarchy]] collapses to its second level.<ref>{{cite journal | last1 = Schöning | first1 = Uwe | author-link = Uwe Schöning | year = 1988 | title = Graph isomorphism is in the low hierarchy | journal = Journal of Computer and System Sciences | volume = 37 | issue = 3| pages = 312–323 | doi=10.1016/0022-0000(88)90010-4| doi-access = free }}</ref> 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]].<ref>{{cite conference|last=Babai|first=László|contribution=Group, graphs, algorithms: the graph isomorphism problem|mr=3966534|pages=3319–3336|publisher=World Sci. Publ., Hackensack, NJ|title=Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures|year=2018}}</ref>

  }}</ref> If graph isomorphism is NP-complete, the [[polynomial time hierarchy]] collapses to its second level.<ref name=":19">{{cite journal | last1 = Schöning | first1 = Uwe | author-link = Uwe Schöning | year = 1988 | title = Graph isomorphism is in the low hierarchy | journal = Journal of Computer and System Sciences | volume = 37 | issue = 3| pages = 312–323 | doi=10.1016/0022-0000(88)90010-4| doi-access = free }}</ref> 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]].<ref name=":20">{{cite conference|last=Babai|first=László|contribution=Group, graphs, algorithms: the graph isomorphism problem|mr=3966534|pages=3319–3336|publisher=World Sci. Publ., Hackensack, NJ|title=Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures|year=2018}}</ref>

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.

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年提出，他的算法是在拟多项式时间解决图的同构问题的。$'''

图同构问题是判定两个有限图是否同构的计算问题。复杂性理论中一个尚未解决的重要问题是图的同构问题是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)|RSA]] algorithm. The integer factorization problem is in NP and in [[co-NP]] (and even in UP and co-UP<ref>[[Lance Fortnow]]. Computational Complexity Blog: [http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html Complexity Class of the Week: Factoring]. 13 September 2002.</ref>). 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)|RSA]] algorithm. The integer factorization problem is in NP and in [[co-NP]] (and even in UP and co-UP<ref name=":21">[[Lance Fortnow]]. Computational Complexity Blog: [http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html Complexity Class of the Week: Factoring]. 13 September 2002.</ref>). 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

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

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

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

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

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

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

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

<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 )</math>

<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 )</math>

==Does P mean "easy"?==

==Does P mean "easy"?==