复杂性-信阳师范学院.ppt

* 定义6 一个算法的最大计算复杂性是指对给定的输入规模，所有实例运行时间的最大值； 一个算法的平均计算复杂性是指对给定的输入规模，所有实例运行时间的平均值。 定义7 设n是输入的规模，一个多项式时间算法是指存在正整数k ，使得计算复杂性为 的算法; 如果对任何正整数k ，算法的计算复杂性都不是为 ，则称该算法为指数时间的算法。 * 粗略地说，多项式时间算法等同于有效的或好的算法，而指数时间算法被认为是无效的算法。 但是，当输入的规模不太大时，这种区分有时并不太合适。 * 在计算复杂性理论中，定义7中的计算复杂性通常指最大计算复杂性。 由于在密码学中，平均复杂性比最大计算复杂性更为重要，因而在密码学中，通常将平均计算复杂性是多项式时间的算法作为多项式时间的算法。 在指数时间的算法中，还有一类复杂性的增长速度介于多项式时间和 O(2n) 的算法，这就是亚指数时间算法。 * 对于亚指数时间的密码破译算法，一定要针对现有和未来几年的计算能力，针对各种输入规模，估计出算法的实际运行时间，从而确定出使破译算法实际可行的最大输入规模。 只有这样，才能准确评测一个密码体制的安全性。 * * * * * * * * * * * * * 四、 问题复杂性 问题复杂性理论主要研究一个问题的固有难度。 一个密码的破译，有时可归结为求解某个典型问题。 如果这个典型问题有一个实际可行的解决方案，那么密码的破译就可实现。 反过来，某些难解的典型问题，又提示人们据此设计不易破译的密码。 因此，掌握一个问题的固有复杂性，对于密码设计和密码分析都具有重要的意义。 * 求解一个典型问题可能有许多算法。 在这些算法中哪种算法是最优的，以及在近期是否可能找到更有效的求解算法，问题复杂性理论可以帮助我们探讨上述问题。 问题复杂性理论以算法复杂性理论为工具，将大量典型的问题按求解的代价进行分类. 对多项式时间内可判定的问题进行分类: P问题、NP问题和NPC问题 特别是在问题复杂性理论研究中，采用所谓多项式变换与图灵归约的分析技巧，从而使大量问题的归类研究变得相对容易。 * 定义9 对于一个问题，如果存在一个算法，使得对该问题的解的每个猜测，都能够输出该猜测正确与否的判定，则称该问题是可判定问题，否则称为不可判定问题。 显然，只有可判定问题，研究其求解算法才有意义。 因此，计算复杂性理论只关心可判定问题。 * 定义10 对于可判定问题，如果存在一个能够解答该问题的每个实例的算法，则称该问题是可解的，否则称该问题是不可解的。 对于不可解问题，一定不存在能够解答该问题的所有实例的算法。通俗地讲，不可解问题就是连答案也没有的问题，因而是可判定问题中最难的问题。不可解问题的确是存在的。 求解一个可解问题可能有许多算法。我们关心的是计算复杂性和存储复杂性的性能最好的那些那些算法，因为该算法的复杂性反映了该问题的固有难度。 * 由于我们关注一个问题的实际可解性，因而一个算法的计算复杂性是多项式时间还是指数时间就显得十分重要了。 定义11 对于一个问题，如果存在一个计算复杂性是多项式时间的求解算法，则称该问题是P问题； 如果存在一个计算复杂性是多项式时间的算法，且该算法能够对该问题的解的每个猜测，输出其正确与否的判断，则称该问题是NP问题。 通俗地讲，NP问题就是对其解的每个猜测，都能实际可行地验证该猜测是否正确的问题，P问题就是能够实际可行地求出其解的问题。 * 显然，P问题一定是NP问题。 但反过来，NP=？P，即NP问题是否都是P问题，这个问题本身也是一个很难的问题，至今还没有解决。 但是，由于有一大批NP问题，人们长期不能证明它们是P问题，故人们倾向于认为NP≠P，即存在不是P问题的NP问题。 密码学中的求解问题，一般多为NP问题。也就是说，对密码分析问题的解的每个猜测，一般都能在多项式时间内判断出该猜测正确与否。 * 在NP问题中，有一类最难的问题，称为NP完全问题，或称为NPC问题。 定义12 称一个NP问题是NPC问题，如果能证明该问题是P问题，蕴涵能够证明所有的NP问题都是P问题。 背包问题就是一个NPC问题，但超递增背包问题却是一个P问题。 这说明即使很难的问题，其子问题却可能是很容易的。 换句话说，尽管没有能够对所有实例都有效的求解算法,但却可能存在对其部分实例都有效的求解。 * 因式分解问题是一个NP问题。至今人们还没有证明因式分解问题是P问题，即没有找到能够在多项式时间内分解所有合数的算法。 但是，对于一些特殊的合数，例如，当p-1的素因子都很小时，