资源描述：
《计算复杂性与抽象代数基础（精品）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六讲计算复杂性与抽象代数基础上海交通大学计算机系龙宇http://cis.sjtu.edu.cn/index.php/Yu_Long内容°计算复杂性°半群群子群°环整环Euclid整环°有限域问题与算法的复杂性°问题Q：需要回答的一般性提问w该问题的全面描述和有关参量w陈述“解”必须满足的性质°问题的实例：将问题的所有参数赋值后所得的特例°问题的规模：或称输入长度，是为解决问题的实例所需输入变量的个数，或者输入二元数据的位数°算法：解决某问题Q的一系列基本步骤或程序算法复杂性及分类°算法复杂性：执行算法所花费的时间或空间代价：时间复杂度和空间复杂度°时间复杂性：简单的说，是
2、解决问题Q的任意实例所花费的最大值°算法复杂性T(n)是g(n)量级：指存在常数c和n1，使得n≥n1时，均有
3、T(n)
4、≤c
5、g(n)
6、。记为T(n)=O(g(n))例：T(n)=kn2+n+1=O(n2)O(n!+n50)=O(n!)O(1)：常数，O(n):线性；O(n2)：二次；O(cn):指数O(nc):多项式时间；O（nlogn）：亚指数时间问题的复杂性及分类°问题的复杂性：简单的说，是解决问题的所有算法中复杂度最小值°P问题：问题Q可以用确定性图灵机在多项式时间内解决°NP问题：问题Q可以用非确定性图灵机在多项式时间内解决°NPC问题：问题Q是NP的，且存在多项
7、式时间内确定性算法能将任意NP问题规约到该问题°P?=NP计算复杂性与密码学的关系°单向函数(onewayfunction)：w是函数f:AÆB，f(x)=yw由任意x∈A求y容易（P）w由“几乎所有”y求x是极为困难的（NP）°陷门单向函数w由x计算f(x)=y很容易（P）w由y计算x很困难（NP）w当某个陷门(trapdoor)k给定，由y,k计算x容易（P）°P≠NP是密码学的必要条件，但不是充分条件一些概念°可忽略的量(negligiblequantity)afunctionE(n):NÆRissaidtobeanegligiblequantityinnifitsre
8、ciprocalisanon-polynomially-boundedquantityinn°不可忽略的量:1-E(n)半群°半群的定义（G,·），G非空w封闭性w结合律°交换半群°单位元°逆元群的基础知识°群的定义：（G,·）w封闭性w结合律w单位元：唯一性w逆元°有限群与无限群°Abelian群（阿贝尔群）：交换群°群同构：f：G→G’，f(ab)=f(a)f(b)为双射°例子w例1：(Z/Q/R/C，+)°单位元/逆元°是无限群，abelian群w例2：(Q*/R*/C*，×)°单位元/逆元°无限群，abelian群°Z*在×下不是群w例3:n个元素的置换组成的集合，置
9、换复合函数°群满足消去定律a,b,c属于群G，则若ab=ac,有b=c子群°定义w（G,·）是群wH是G的非空子集wH在·运算下仍是群w记做H≤G例:在+运算下（1）Z≤Q≤R≤C（2）{0,偶数}≤Z°群的任意个子群的∩，仍然是群（子群）°但子群的∪一般不是子群°子集生成的子群群/群元素的阶与循环群°群的阶w有限群（G,·）中，集合元素的个数，记为
10、G
11、°群元素的阶wa∈G,
12、a
13、为使ak=e的最小k,记为
14、a
15、wad=e,k
16、d°H≤G,则一定有
17、H
18、
19、
20、G
21、(Lagrange定理）°推论1：a∈G，则
22、a
23、
24、
25、G
26、,
27、a
28、代表a的阶，也等于a所生成子群的阶°推论2；a∈
29、G,
30、a
31、=n,则
32、ak
33、=n/(n,k)°循环群w群（G,·），a∈G,ai=a·a·…·a;a0=e；a-n=(a-1)nwG=(a)={a0,a1,…,an-1}，
34、G
35、=
36、a
37、w分类°无限循环群，阶为无穷大°有限循环群，n阶，
38、a
39、=
40、(a)
41、=n例：（Z,+）是无限循环群环°定义：（R，+,×）w（R,+）是交换群（封闭、可结合、逆元、交换）w（R,×）是半群（封闭、可结合）w×对+满足分配律°零元：+的单位元，记为0，任意a∈R,0a=0°单位元：一般指×的单位元°交换环：指对×满足交换性°a∈R,ka=a+a+…+a(k个a相+）°a∈R,ak=a×a×…×a(
42、k个a相×）环举例°例1：整数、有理数、实数、复数对加法和乘法（数环）°例1：实数上n阶方阵的集合对加法和乘法°例2：偶整数集合（正、负、0）对普通加法和乘法°例3：多项式环，设A为数环多项式集A[x]=a+ax+ax2+…+axn012n+定义为(a,a,…)+(b,b,…)=(a+b,a+b,…)01010011×定义为(a,a,…)×(b,b,…)=(c,c,…)010101caki=∑bjijk+=环的零因子与环的特征对于环（R，+,×）°零因子：a,b∈R,且a,b≠0,若ab=0，a是R的左
