计算复杂性与抽象代数基础.pdf

第六讲计算复杂性与抽象代数基础 上海交通大学计算机系 龙 宇 /index.php/Yu_Long 内容 计算复杂性 半群群子群 环整环Euclid整环 有限域 问题与算法的复杂性 问题Q：需要回答的一般性提问 该问题的全面描述和有关参量 陈述“解”必须满足的性质 问题的实例：将问题的所有参数赋值后所得的特例 问题的规模：或称输入长度，是为解决问题的实例 所需输入变量的个数，或者输入二元数据的位数 算法：解决某问题Q的一系列基本步骤或程序 算法复杂性及分类 算法复杂性：执行算法所花费的时间或空间代价： 时间复杂度和空间复杂度 时间复杂性：简单的说，是解决问题Q的任意实例 所花费的最大值 算法复杂性T(n)是g(n)量级：指存在常数c和n1，使 得n≥n1时，均有|T(n)|≤c|g(n)| 。记为T(n)=O(g(n)) 例：T(n)=kn2 2 +n+1=O(n ) O(n!+n50)=O(n!) O(1)：常数，O(n):线性；O(n2 n ) ：二次；O(c ):指数 O(nc):多项式时间；O （nlog n ）：亚指数时间 问题的复杂性及分类 问题的复杂性：简单的说，是解决问题的所有算法 中复杂度最小值 P问题：问题Q可以用确定性图灵机在多项式时间内 解决 NP问题：问题Q可以用非确定性图灵机在多项式时 间内解决 NPC问题：问题Q是NP的，且存在多项式时间内确 定性算法能将任意NP问题规约到该问题 P?=NP 计算复杂性与密码学的关系 单向函数(one way function)： 是函数f: AB，f(x)=y 由任意x ∈A求y容易 （P） 由“几乎所有”y求x是极为困难的（NP） 陷门单向函数 由x计算f(x)=y很容易（P） 由y计算x很困难（NP） 当某个陷门(trapdoor) k给定，由y, k计算x容易（P） P≠NP是密码学的必要条件，但不是充分条件 一些概念 可忽略的量(negligible quantity) a function E (n): NR is said to be a negligible quantity in n if its reciprocal is a non-polynomially-bounded quantity in n 不可忽略的量: 1- E (n) 半群 半群的定义（G, ·），G非空 封闭性 结合律 交换半群 单位元 逆元 群的基础知识 群的定义：（G, ·） 封闭性 结合律 单位元：唯一性 逆元 有限群与无限群 Abelian群（阿贝尔群）：交换群 群同构：f ：G→G’，f(ab)=f(a)f(b)为双射 例子 例1： (Z/Q/R/C，+) 单位元/逆元 是无限群，abelian群 例2：(Q*/R*/C*，×) 单位元/逆元 无限群，abelian群 Z*在×下不是群 例3: n个元素的置换组成的集合，置换复合函数 群满足消去定律 a,b,c属于群G，则若ab=ac,有b=c 子群 定义 （G, · ）是群 H是G的非空子集 H在·运算下仍是群 记做H≤G 例: 在+运算下 （1）Z ≤Q ≤R ≤C （2 ）{0,偶数} ≤Z 群的任意个子群的∩，仍然是群（子群） 但子群的∪一般不是子群 子集生成的子群 群/群元素的阶与循环群 群的阶 有限群（G, ·）中，集合元素的个数，记为|G| 群元素的阶