第4章 密码学的计算复杂性理论基础.ppt

第4章密码学的计算复杂性理论基础
问题与算法的复杂性
问题与语言
. 整数的因子分解问题。
. 背包问题。
实际应用中的绝大多数问题都可直接或间接地转化为判定问题。
的任一子集L称为一个B-语言(或简称语言)。语言L中的字称为语言L的成员。
设一个语言已给定。语言L成员的识别问题可描述为:任给(参数),问是否x是L语言的成员(是否)?
设为一个问题,B为一个字符集。从I到中的一个映射c,满足条件(空集),称为问题D的一个B-编码。若c为D的一个编码,集称为D的一个c-语言。
若c为D的一个编码,则求解问题D和求解语言的成员识别问题是等价的,即问题D的任一例子,其答案与语言的成员识别问题的例子的答案是相同的。
一个合理编码还应满足下列两个基本要求:
1) 编码是容易实现的;
2) 求解问题的任一例子的计算复杂性(通常用计算时间来表示)与的长有某种正比关系。
算法与图灵机
….
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
8
…无限长磁带
有限状态控制器
读写头
确定性单带图灵机示意图
定义 一个确定性单带图灵机由下列集和函数构成。
1. 1)带中所用字符集B,通常可设,其中表示空。
2)读写头所处的可能状态集S,其中包含一个初始状态和若干个停机状态。
3)读写头所处状态的转移函数,它是读写头现在所处状态s和所读字符b的函数,表示为。
4)读写头动作的指令函数,它也是读写头现在所处状态s和所读字符b的函数,表示为,其中且都不属于B。若,则读写头写字符代替b,且保持原位不动。若,则原字符b保持不变,读写头向左(或向右)移动一个小方格。
2. 磁带上的每个小方格用一个整数坐标i表示。小方格i中的字符记作t(i),磁带表示为函数。
3. 图灵机在某一时刻的形是指一个三元组,它们分别表示该时刻读写头所处状态,磁带和读写头所扫描的小方格坐标,t(i)为读写头在该时刻所读字符。
一个图灵机的计算程序(算法)是一个形的有限或无限序列,其中为图灵机在初始时刻的形,即为初始状态,为初始磁带,它由输入数据(字) 给出,通常存放在小方格中,其它小方格中为空字符,通常。图灵机在k时刻的形由下面的递推式给出。

若存在形使,则计算在时刻终止,同时停机,称或为计算的输出结果,K称为图灵机(算法)的运行(计算)时间。否则计算将不终止,不停机,直到无限。
定义 称一个图灵机 M可解一个语言L 的成员识别问题,若对任一输入数据,M在有限时刻停机,且M的输出,若。否则。图灵机的计算复杂性定义为
定义 设f(n)和g(n)为两个正整数函数,若存在正整数和常数c使当时有,则记作;若, ,则记作
设和为图灵机M和的计算复杂性,若,则称算法不比算法M有效;若,则称算法M和是等效的;若存在正整数d, ,则称M为多项式时间算法,按密码学中的传统观念,认为多项式时间算法为有效算法;若,则称M为亚指数时间算法;若,则称M为指数时间算法。亚指数和指数时间算法也被称为超多项式时间算法,被认为不是有效算法。
问题的计算复杂性分类
P,NP,NP完全类问题
一个语言L的成员识别问题属于P类,若存在一个可解该问题的图灵机M和一个正多项式,使M的计算复杂性,所有P类问题构成的集记作P。
一个语言L的成员识别问题属于NP类,若存在一个的子集(称为一个布尔关系)及一个正多项式p(n)满足下列两个条件:
1) 的成员识别问题属于P类;
2) 当且仅当存在一个y,其长,且。这样的y称为是的证据。所有NP类问题构成的集记作NP。