别表示该时刻读写头所处状态，磁带和读写头所扫描的 小方格坐标，t(i)为读写头在该时刻所读字符。
4. 一个图灵机的计算程序（算法）是一个形的有限或无限
序列(s0 ,t0 ,i0 ), (s1,t1,i1), (s2 ,t2 ,i2 ), ，其中(s0 ,t0 ,i0 )为图灵机在初
始时刻的形，即 数据（字）x B*
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 0,1,，其中 表示空。
第4章 密码学的计算复杂性 理论基础
4.1 问题与算法的复杂性
• 4.1.1 问题与语言
– 例4.1 . 整数的因子分解问题。
– 例4.2 . 背包问题。
实际应用中的绝大多数问题都可直接或 间接地转化为判定问题。
• 定义4.1 B*的任一子集L称为一个B－语言（或
简称语言）。语言L中的字称为语言L的成员。 • 定义4.2 设一个语言L B*已给定。语言L成员
的识别问题可描述为：任给 x B（* 参数），问 是否x是L语言的成员（是否 x L）？ • 定义4.3 设D (I, I 为) 一个问题，B为一个字符 集。从I到 B*中的一个映射c，满足条件c(I ) c(I ) （空集），称为问题D的一个B－编码。若c为
D的一个编码，集 L(D,c) c( ); I c(I ) 称为


b tk (i) tk1 (i)
i ik1 i ik1
(4.3)
若若((sskk11,,ttkk11((iikk11))))

l r
则tk tk1, ik ik1 1 则tk tk1, ik ik1 1
若存在形 (sk ,tk ,ik ) 使 sk T ，则计算在时刻 K min( k; sk T ) 终止，同时停机，称 (tk ,ik ) 或 tk (ik ) 为计算的输出结果，K 称为图灵机（算法）的运行（计算）时间。否则计算将 不终止，不停机，直到无限。
(n)

(
p(n))
，所有P类问题构成
• 定义4.9 一个语言L的成员识别问题属于NP类，若存
在一个 0,1* 0,1*的子集 RL (x, y) （称为一个布尔关系）
及一个正多项式p(n)满足下列两个条件：
1）RL 的成员识别问题属于P类；
给s 0为出初，始通状常态存，放t0为在初1 始x磁小带方，格它中由，输其入
它形小(sk方,tk格,ik 中), k 为 1空,2,字由符下 面，的通递常推i0 式 1给。出图。灵机在k时刻的
若(sk1, tk1 (ik1 )) b B 则ik ik1
sk (sk1 , tk1 (ik1 ))
• 定义 4.5 称一个图灵机 M可解一个语言
L 的成员识别问题,若对任一输入数
据 x 0,1*，M在有限时刻 K(x)停机，且M
的输出 ，若 。否则 。 tK(x) (iK(x) ) 1
xL
t K (x) (iK (x) ) 0
图灵机的计算复杂性定义为
f
M
(n)

maxK
x; x n
(
x)
• 定义 4.6 设f(n)和g(c使当 时n n0 有 f (n) cg(n)，则记作 f (n) (g(n)) ；
若 f (n) (g(n)) ， g(n) ( f (n)) ，则记作
f (n) Θ （g(n))
• 定义4.7 设 fM (n)和 fM ' (n)为图灵机M和 M '的 计算复杂性，若 fM (n) ( fM' (n))，则称算法 M ' 不比算法M有效；若 fM (n) ( fM' (n)) ，则称算 法M和M '是等效的；若存在正整数d， fM (n) (nd )，则称M为多项式时间算法，按 密码学中的传统观念，认为多项式时间 算法为有效算法；若 fM (n) (2logn ) ，则称M 为亚指数时间算法；若 fM (n) ， (2n )或（10n )
2）读写头所处的可能状态集S，其中包含一个初始状态
和若干个停机状态
。
s0
3）读写头所处状态T的转S 移函数 ，它是读写头现在所处状
态s和所读字符b的函数，表示为
。
4）读写头动作的指令函数 ，它也: S是读B 写S头现在所处状态s
和所读字符b的函数，表示为
，其中
且都不属于B。若
: S， B则读B 写l,头r 写字符 l代替r b，
D的一个c－语言。
• 引理4.1 若c为D的一个编码，则求解问题D和 求解语言 L(D,c)的成员识别问题是等价的，即
问题D的任一例子 I，其答案与语言L(D,c)的
成员识别问题的例子的答案 c( )是相同的。
• 一个合理编码还应满足下列两个基本要求：
1） 编码是容易实现的；
2） 求解问题的任一例子的计算复杂性（通常 用计算时间来表示）与的长有某种正比关系。
则称M为指数时间算法。亚指数和指数 时间算法也被称为超多项式时间算法， 被认为不是有效算法。
4．2 问题的计算复杂性分类
• 4.2.1 P，NP，NP完全类问题
• 定义4.8 一个语言L的成员识别问题属于P类，若存在
一个可解该问题的图灵机M和一个正多项式 p(n)，使
M的计算复杂性 的集记作P。
fM
且保持原位不动。若(s,b) b' B
，则原字符b保持b ' 不变，
读写头向左（或向右）移动(s一,b)个 l小(或方r) 格。
2. 磁带上的每个小方格用一个整数坐标i表示。小方格i中的字
符记作t(i)，磁带表示为函数
。
t : Z (整数集） B
3. 图灵机在某一时刻的形是指一个三元组(s, t, i)，它们分