当前位置:文档之家› 计算复杂性

计算复杂性

: {,}
若控制器当前状态为 且n 读写头指向方格内容为 ,n 转 移函数 ( n,可n完) 成如下工作:
若 n h,则计算停止(也称停机),否则确定控制器的下一步
状态 n1 ;
修改读写头指向方格内容,将其改为 n1; 确定读写头移动的方向,要么向左(←),要么向右(→)。来自 问题的难度概率多项式时间
PP机(Probabilistic Polynomial-time Machine) :
存在多项式界限且没有未知状态的PTM。
PP机满足两类概率的界限:
❖ 输入I属于语言L时,PTM识别该输入属于语言L的概率, 这是一种正确概率:
Pr[PTM recognizes I L | I L] C
控制器
... *
读写头
0
1
1
0
纸带
1
*
*
...
确定型图灵机
问题的难度
定义8.5 P 确定型图灵机上的具有有效算法的 判定问题之集合。
Cook-Karp论题:L是易解的当且仅当L∈P;
得出的问题的难度的定义为:
某问题存在有效算法则称之为易解(Tractable) 的;如果它不存在多项式算法,则称它是难解 的(Intractable)。它与Cook-Karp论题等价。
(c其), 中(loOg(nc)),一(般n),写(成n lOog(n1)),,(它n2)是, 理(2论n), 上(n的!)最, (佳nn算) 法; O(n)称为线性算法,它是实际中常见的最好算法;而 O(nn)是最差算法,相当于穷举搜索。
算法效率分析
定义8.3 有效算法(Efficient Algorithm) 时间复杂度为O(nk)(k∈N)的算法是有效算
❖ 多项式时间不可区分性。
8.1 确定性多项式时间
8.1.1 算法效率分析
什么是算法? 算法(Algorithm)即是在有限步骤内求解某
一问题所使用的一组定义明确的规则。
如何衡量算法的效率? 使用复杂度来衡量算法的效率。
算法效率分析
定义8.1 复杂度
❖ 时间复杂度(Time Complexity):该算法完全运行所 需运算时间的多少。通常采用阶(Order)的概念来描
号均属于∑,除了有限个方格外,其它方格上的符号均为*; ❖ 读写头:可在任一时刻对某个确定的方格进行操作。此读写头可向
左(←)或向右(→)移动;
❖ 控制器:它携带状态集Γ,包括特定的起始状态 和0 停机状态集 h。
问题的难度
DTM的计算可由转移函数(Transition Function)决定:
❖ 输入I不属于语言L时,PTM识别该输入属于语言L的概率, 这是一种错误概率:
Pr[PTM recognizes I L | I L] E
BPP机(Bounded Probabilistic Polynomial-time Machine)
界限为
1 2
C
1

0 E
1 2
的PTM。
概率多项式时间
法。多项式算法是有效算法。
8.1.2 问题的难度
如何判断问题的难度: 如果一个问题存在有效算法解决之,则可
认为它是较“简单”的问题,反之则可认为 它是较“困难”的问题。
问题的难度
定义8.4 确定型图灵机(Deterministic Turing Machine) 一台DTM由如下要素组成:
❖ 符号表∑:∑由有限个符号组成,包括标识空白的特殊字符*; ❖ 可双向移动的无限长纸带:该纸带由无限个方格组成,方格上的符
非确定多项式时间
定义8.6 NP:非确定型图灵机上的存在有效算 法的判定问题之集合。 NP完全(NP-Complete, NPC)问题:
满足既找不到有效算法,又不能确定它不 存在有效算法,但是如果其中一个存在有效算 法,那么此类问题均存在有效算法的问题。
非确定多项式时间
NP问题
P问题
NP完全问题
:当且仅当 f (n) (g(n与)) f (n) ,(g(称n))
f (n) O(g(n)) f (n) (g(n)) f (n) (g(n))
算法效率分析
通常分析时间的渐进复杂度,常使用O记号,指明 算法的上界。Θ记号更为精确,但难以估算,较少采用。
常用的阶按照增长速度递增排序为:
NP中各类问题的关系
8.3 概率多项式时间
定义8.7 概率图灵机(Probabilistic Turing Machine, PTM) :
它可以看成一台总停机的NTM,它在每个 格局至多有两个格局,从当前格局等可能的到 达其中之一。PTM停机的状态有三种:接受、 不接受和未知。如果PTM停机在未知状态,称 该计算无效。
8.2 非确定多项式时间
非确定型图灵机(NTM, Non-deterministic Turing Machine) NTM在进行计算的时候,会自动选择最优路径
进行计算。 NTM进行计算时,碰到需要选择的分支,则对 自身进行复制,每个分支分配一个副本进行计 算,这样也只需要多项式时间即可判定其可满 足性。
定义8.8 广义的有效算法 在DTM或PP机下的多项式算法是有效算法。
定义8.9 Monte Carlo算法 满足下列特点的概率算法:
Pr[PTM recognizes I L | I L] 1 Pr[PTM recognizes I L | I L] E
概述
Oded Goldreich提出定义“安全”的两种途 径:
❖ 基于信息论的经典方法:度量密文中包含 明文的信息量。
❖ 基于计算复杂性的现代方法:给出破解密 文的难度。
本章内容
❖ 介绍确定型图灵机、非确定型图灵机、概率 图灵机这三个基本计算模型;
❖ 在三种图灵机的基础上讨论NP完全问题和加 密体制是否安全之间的关系;
述时间复杂度。
❖ 空间复杂度(Space Complexity):该算法完全运行所 需存储空间的大小。
算法效率分析
定义8.2 渐进记号(Asymptotic Notation)
假定f ()、g() 均为非负函数,定义域均为N。问题的输
入规模为n,为描述渐进复杂度中的阶,定义如下记号:
O:当且仅当 c, n0,n(n n0 f (n) c, g称(n)) :当且仅当c, n0,n(n n0 f (n) c, g称(n))
相关主题