第4章密码学的计算复杂性 理论基础
第4章 密码学的计算复杂性 理论基础
4.1问题与算法的复杂性 4.1.1问题与语言 -例4.1.整数的因子分解问题 -例4.2.背包问题。 实际应用中的绝大多数问题都可直接或 间接地转化为判定问题
4.1 问题与算法的复杂性 • 4.1.1 问题与语言 – 例4.1 . 整数的因子分解问题。 – 例4.2 . 背包问题。 实际应用中的绝大多数问题都可直接或 间接地转化为判定问题
定义41B的任一子集L称为一个B一语言(或 简称语言)。语言中的字称为语言L的成员 定义42设一个语言cB已给定。语言L成员 的识别问题可描述为:任给x∈B参数),问 是否x是L语言的成员(是否x∈L) 定义43设D=(1,一个问题,B为一个字符 集。从工到B中的一个映射c,满足条件c()ac( (空集),称为问题D的一个B一编码。若c为 D的一个编码,集L(Dc)={(O)∈}=c()称为 D的一个C一语言
• 定义4.1 的任一子集L称为一个B－语言（或 简称语言）。语言L中的字称为语言L的成员。 • 定义4.2 设一个语言 已给定。语言L成员 的识别问题可描述为：任给 （参数），问 是否x是L语言的成员（是否 ）？ • 定义4.3 设 为一个问题，B为一个字符 集。从I到 中的一个映射c，满足条件 （空集），称为问题D的一个B－编码。若c为 D的一个编码，集 称为 D的一个c－语言。 * B * L B * x B x L ( , ) + D = I I * B = + − c(I ) c(I ) ( , ) ( ); ( ) + + L D c = c I = c I
引理4.1若c为D的一个编码,则求解问题D和 求解语言L(D,c)的成员识别问题是等价的,即 可题D的任一例子b∈l,其答案与语言L(D,c 成员识别问题的例子的答案c(O)是相同的 合理编码还应满足下列两个基本要求 1)编码是容易实现的 2)求解问题的任一例子的计算复杂性(通常 用计算时间来表示)与的长有某种正比关系
• 引理4.1 若c为D的一个编码，则求解问题D和 求解语言 的成员识别问题是等价的，即 问题D的任一例子 ，其答案与语言 的 成员识别问题的例子的答案 是相同的。 • 一个合理编码还应满足下列两个基本要求： 1） 编码是容易实现的； 2） 求解问题的任一例子的计算复杂性（通常 用计算时间来表示）与的长有某种正比关系。 L(D,c) I L(D,c) c( )
4.1.2算法与图灵机 有限状态控制器 读写头 无限长 磁带 图41确定性单带图灵机示意图
4.1.2 算法与图灵机 …. -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 …无限长 磁带 有限状态控制器 读写头 图4.1 确定性单带图灵机示意图
定义4.4一个确定性单带图灵机由下列集和函数构成 1.1)带中所用字符集B,通常可设B=01x},其中4表示空 2)读写头所处的可能状态集S,其中包含一个初始状态 和若干个停机状态 3)读写头所处状态的转移函数,它是读写头现在所处状 态s和所读字符b的函数,表示为 4)读写头动作的指令函数,它也彩头现在所处状态s 和所读字符b的函数,表示沟 其中 且都不属于B。若 k:×-以写字符张替b, 且保持原位不动。s,b)=b∈B,则原字符b保持不变 读写头向左(或向右)移s,b))方格。 2.磁带上的每个小方格用一个整数坐标表示。小方格i中的字 符记作t(),磁带表示为函数 t:Z(整数集)→B
• 定义 4.4 一个确定性单带图灵机由下列集和函数构成。 1. 1）带中所用字符集B，通常可设 ，其中 表示空。 2）读写头所处的可能状态集S，其中包含一个初始状态 和若干个停机状态 。 3）读写头所处状态的转移函数 ，它是读写头现在所处状 态s和所读字符b的函数，表示为 。 4）读写头动作的指令函数 ，它也是读写头现在所处状态s 和所读字符b的函数，表示为 ，其中 且都不属于B。若 ，则读写头写字符 代替b， 且保持原位不动。若 ，则原字符b保持不变， 读写头向左（或向右）移动一个小方格。 2. 磁带上的每个小方格用一个整数坐标i表示。小方格i中的字 符记作t(i)，磁带表示为函数 。 B = 0,1, 0 s T S : S B →S : S B → Bl,r l r s b = b B ' ( , ) ' b (s,b) = l(或r) t : Z(整数集）→ B
3.图灵机在某一时刻的形是指一个三元组(S,t,i),它们 别表西该时刻读写头所处状态,磁带和读写头所扫描的 4.一个图灵机的计算程序(算法)是一个形的有限或无限 序列(s,ti)(s1,,i)(s2l2l2)…, 其中(s,,)图灵机在初 始时刻的形,即S为初始状态,为初始磁带,它由输入 数据(字)x∈B给出,通常存放在1-小方格中,其 它小方格中为空字符λ,通常i=1。图灵机在k时刻的 形(.)k=12…由下面的递推式给出 若以(S121k1(1)=b∈B则;=i1 SI =o(s k-11k-1(k-1 (i= (4.3) 若(S1,k1(ik1)=l则t4=k1,bk=ik1-1 若4(S1,t1=1(i=1)=r则tk=tk-1,ib=i 若存在形(sk,)使Sk∈T,则计算在时刻K=m(k,sk∈7) 终止,同时停机,称()或()为计算的输出结果,K 为图灵机(算法)的运行(计算)时间。否则计算将 )不停机,直到无限
3. 图灵机在某一时刻的形是指一个三元组 ，它们分 别表示该时刻读写头所处状态，磁带和读写头所扫描的 小方格坐标，t(i)为读写头在该时刻所读字符。 4. 一个图灵机的计算程序（算法）是一个形的有限或无限 序列 ，其中 为图灵机在初 始时刻的形，即 为初始状态，为初始磁带，它由输入 数据（字） 给出，通常存放在 小方格中，其 它小方格中为空字符 ，通常 。图灵机在k时刻的 形 由下面的递推式给出。 若存在形 使 ，则计算在时刻 终止，同时停机，称 或 为计算的输出结果，K 称为图灵机（算法）的运行（计算）时间。否则计算将 不终止，不停机，直到无限。 (s,t,i) (s0 ,t 0 ,i 0 ),(s1 ,t 1 ,i 1 ),(s2 ,t 2 ,i 2 ), ( , , ) 0 0 0 s t i 0 s 0 t * x B 1− x i 0 = 1 (sk ,t k ,i k ), k =1,2, ( , ( )) k = k−1 k−1 k−1 s s t i = = = + = = = − = = = = − − − − − − − − − − − − − − − − − ( , ( )) , 1 ( , ( )) , 1 (4.3) ( ) ( ) ( , ( )) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 k k k k k k k k k k k k k k k k k k k k k k k s t i r t t i i s t i l t t i i t i i i b i i t i s t i b B i i 若 则 若 则 若 则 ( , , ) k k k s t i sk T K min( k;s T) = k ( , ) k k t i ( ) k k t i
定义45称一个图灵机M可解一个语言 L的成员识别问题,若对任一输入数 据x∈0},M在有限时刻K(x)停机,且M 的输出s 若x∈L。否则 图灵机的计算复杂性定义为 fM(n)=max[k(x) Xx=n 定义46设f(n)和g(n)为两个正整数函数, 若存在正整数和常数c使当时≥n 有(m)scgm,则记作f(m)=Og(m); l)=O(g(m),g(m)=O(/(m),则记作 f(n)=⊙(g(m)
• 定义 4.5 称一个图灵机 M可解一个语言 L 的成员识别问题,若对任一输入数 据 ，M在有限时刻 停机，且M 的输出 ，若 。否则 。 图灵机的计算复杂性定义为 • 定义 4.6 设f(n)和g(n)为两个正整数函数， 若存在正整数 和常数c使当 时 有 ，则记作 ； 若 ， ，则记作 * x 0,1 K(x) t K( x) (i K( x) ) = 1 x L t K( x) (i K( x) ) = 0 ( ) max ( ) ; f n K x x x n M = = 0 n n n0 f (n) cg(n) f (n) = (g(n)) f (n) = (g(n)) g(n) = ( f (n)) f (n) =Θ（g(n))
定义4.7设(m)和/(为图灵机M和M的 计算复杂性,若f(=O(m),则称算法M 不比算法M有效;若/(m)=(m),则称算 法M和M是等效的:若存在正整数d, ∫n(m)=On),则称M为多项式时间算法,按 密码学中的传统观念,认为多项式时间 算法为有效算法;若f)=2),则称M 为亚指数时间算法;若/m)=2或0), 则称M为指数时间算法。亚指数和指数 时间算法也被称为超多项式时间算法, 为不是有效算法
• 定义4.7 设 和 为图灵机M和 的 计算复杂性，若 ，则称算法 不比算法M有效；若 ，则称算 法M和 是等效的；若存在正整数d， ，则称M为多项式时间算法，按 密码学中的传统观念，认为多项式时间 算法为有效算法；若 ，则称M 为亚指数时间算法；若 ， 则称M为指数时间算法。亚指数和指数 时间算法也被称为超多项式时间算法， 被认为不是有效算法。 f (n) M f ' (n) M ' M f (n) ( f ' (n)) M M = ' M f (n) ( f ' (n)) M M = ' M ( ) ( ) d f M n = n ( ) (2 ) logn f M n = ( ) (2 ) 10 ) n n f M n = 或（
4.2问题的计算复杂性分类 4.21P,NP,NP完全类问题 定义48一个语言L的成员识别问题属于P类,若存在 个可解该问题的图灵机M和一个正多项式p(m),使 M的计算复杂性f(n)=O(D(m),所有P类问题构成 的集记作P。 定义49一个语言的成员识别问题属于NP类,若存 在 o0×⑨的子集R={xy)}(称为一个布尔关系) 及一个正多项式p(n)满足下列两个条件: 1)R2的成员识别问题属于P类 2)x∈L当且仅当存在一个y,其长川以(x),且(xy)∈B 这样的y称为是x∈L的证据。所有NP类问题构成的集 记作N
4．2 问题的计算复杂性分类 • 4.2.1 P，NP，NP完全类问题 • 定义4.8 一个语言L的成员识别问题属于P类，若存在 一个可解该问题的图灵机M和一个正多项式 ，使 M的计算复杂性 ，所有P类问题构成 的集记作P。 • 定义4.9 一个语言L的成员识别问题属于NP类，若存 在一个 的子集 （称为一个布尔关系） 及一个正多项式p(n)满足下列两个条件： 1） 的成员识别问题属于P类； 2） 当且仅当存在一个y，其长 ，且 。 这样的y称为是 的证据。所有NP类问题构成的集 记作NP。 p(n) f (n) (p(n)) M = * * 0,1 0,1 RL = (x, y) RL x L y p( x ) RL (x, y) x L