计算困难假设如何影响算法复杂性分析？

本文共计1427个文字，预计阅读时间需要6分钟。

以下是对原文的简化

在计算复杂性理论中，计算困难假设是一个特定的假设问题，指的是在多项式时间内无法找到有效解的问题。目前还不清楚如何证明其困难性。

以下内容翻译自：维基

介绍

在计算复杂性理论中，计算困难假设是一个特定问题无法得到有效解决的假设（有效通常指“在多项式时间内”）。目前还不知道如何证明其困难性。同时，我们可以将一个困难问题规约到（reductions）一个比较容易理解的问题上。

多项式时间
常见的时间复杂度从小到大：

\[O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!) \]

只要算法的复杂度不会是最后两个指数或者阶乘型，前面的\(O(1)\)到\(O(n^m)\)（\(m\)为常数）任意组合都算是多项式级的复杂度，它们的规模\(n\)都出现在底数位置；而\(O(2^n)，O(n!)\)型 复杂度，就是非多项式级的，问题规模较大时，计算机也很难算出结果。所以我们一般会选择多项式级复杂度的算法。

在密码学中，计算困难假设是非常重要的。可以这么说，"只要给出一个困难问题，就能构造一个公钥加密方案"。通常一个加密方案，需要具有信息论上的安全（information theoretic security），也就是满足一次一密（one-time pad），然而信息论上的安全一般是难以实现的。