第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 确定性单带图灵机示意图