561
个编辑
更改
跳到导航
跳到搜索
第1,030行：
第1,030行： − + 第1,108行：
第1,108行： − −
→Problems in NP not known to be in P or NP-completeNP中不知是P中或NP完全问题的问题
===Problems in NP not known to be in P or NP-completeNP中不知是P中或NP完全问题的问题===
===Problems in NP not known to be in P or NP-completeNP中不知是P或NP完全问题的问题===
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 prime 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). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.
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 prime 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). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.
然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。
然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。
===Separations between other complexity classes其他复杂性类之间的分离===
===Separations between other complexity classes其他复杂性类之间的分离===