视频：地址

本章的主要内容：问题的定义和分类、算法复杂度的定义和分类、P问题和NP问题、规约思想和NPC问题、密码算法的计算安全性

问题的定义和分类

背包问题

数学化定义：

是NP问题！

素数分解问题

无法证明是P问题还是NP问题!

问题定义

问题：描述参量陈述揭发应满足的性质（询问）

参量是具体数值时，称为问题的一个实例

判定问题：回答是或否

计算问题：从其可解集合中搜索出最优解

算法复杂性的定义和分类

复杂度

时间（计算）复杂度：考虑算法的主要操作步骤，计算执行中所需的总操作次数

空间复杂性：执行过程中所需存储器的单元数目

数据复杂度：信息资源

计算模型

使用 确定性图灵机（有限带符号集合、有限状态集、转换函数）来判断复杂度

P问题和NP问题

P问题一般认为是多项式问题，即该问题在多项式时间被解决的问题；而多项式问题被认为是简单问题，即一个算法的复杂度是P问题或难度和P问题一样的话，该算法被认为是不安全的！

P问题

如何一个判定问题存在解它的多项式时间的算法，则该问题属于P类问题

NP问题

如果一个判定问题不存在解它的多项式时间的算法，且对于一个解答（猜）可以在多项式时间验证其是否正确，则称该问题属于NP类问题

那么P问题是否是NP问题？
更多：参考

密码算法的计算安全性

可以看出，不同的算法，算法复杂度有很大的不同！

当问题输入长度足够大，分析密码*的算法复杂度较大，可能的计算能力下，在保密的期间可以保证算法不被攻破，这就是密码*的算法安全性思想！

好的密码系统设计：

　　合法用户：简单（多项式时间）

　　攻击者：复杂（非多项式时间）

实际安全是指密码系统满足以下准则：

1、破解该密码系统的成本超过被加密信息本身的价值

2、破译该密码系统的时间超过被加密信息的有效生命周期