8.2节P类与NP类问题.ppt

P类与NP类问题 POWERPOINT 目录 多项式时间验证 P类与NP类语言 非确定性图灵机 引言 时间复杂度并不是表示一个程序解决问题需要花多少时间 而是当问题规模扩大后 程序需要的时间长度增长得有多快 不管数据有多大 程序处理花的时间始终是那么多的 我们就说这个程序很好 具有O 1 的时间复杂度 也称常数级复杂度 数据规模变得有多大 花的时间也跟着变得有多长 这个程序的时间复杂度就是O n 引言 多项式级的复杂度 如O 1 O log n O n a 等 因为它的规模n出现在底数的位置 时间复杂度 非多项式级的如 O a n 和O n 等 引言 多项式时间算法 如果 是任意一个问题 对 存在着一个算法 它的时间复杂性为O nk 其中n为输入规模 k为非负整数 就认为存在着一个解问题 的多项式时间算法 引言 有许多问题 从表面上看似乎并不比排序或图的搜索等问题更困难 然而至今人们还没有找到解决这些问题的多项式时间算法 也没有人能够证明这些问题需要超多项式时间下界 在图灵机计算模型下 这类问题的计算复杂性至今未知 为了研究这类问题的计算复杂性 人们提出了另一个能力更强的计算模型 即非确定性图灵机计算模型 简记为NDTM NondeterministicTuringMachine 一 非确定性图灵机 在图灵机计算模型中 移动函数 是单值的 即对于Q Tk中的每一个值 当它属于 的定义域时 Q T L R S k中只有唯一的值与之对应 称这种图灵机为确定性图灵机 简记为DTM DeterministicTuringMachine 7 一 非确定性图灵机 非确定性图灵机NDTM提出了另一个能力更强的计算模型非确定性图灵机完全是一种假想的机器非确定性图灵机允许移动函数 具有不确定性 Q Tk Q T L R S k Q T L R S k为Q T L R S k的一个子集 q x1 x2 xk 可在该子集中中随意选定一个值作为它的函数值 8 一 非确定性图灵机 确定性与非确定性图灵机的区别 确定性图灵机 每一步只有一种选择 非确定图灵机 每一步可以有多种选择 9 NP 二 P类与NP类语言 如果一个问题可以找到一个能在多项式的时间里解决它的算法 那么这个问题就属于P问题 P类问题P DTM能在多项式时间内所接受的语言类 对于所有与DTM等价的计算模型来说 P是不变的 P大致对应计算机上实际可解的那类问题排序问题矩阵连乘问题最小生成树问题图搜索问题 二 P类与NP类语言 也称为 难解问题例 旅行售货员问题 团问题特点 问题有解 蛮力搜索 时间复杂性是指数函数时间还未发现多项式时间DTM算法引入新的计算能力更强的计算模型 NP类语言定义 NP L L是一个能在多项式时间内被一台NDTM所接受的语言 二 P类与NP类语言 不确定性算法猜想阶段在多项式时间内产生一个任意字符串yy可能对应输入实例的解 也可能不是解验证阶段使用确定性算法验证字符串y是否解验证算法要求在多项式时间内完成 二 P类与NP类语言 NP类语言举例 无向图的团问题 该问题的输入是一个有n个顶点的无向图G V E 和一个整数k 要求判定图G是否包含一个k顶点的完全子图 团 即判定是否存在V V V k 且对于所有的u v V 有 u v E 若用邻接矩阵表示图G 用二进制串表示整数k 则团问题的一个实例可以用长度为的二进位串表示 因此 团问题可表示为语言 CLIQUE w v w v 0 1 以w为邻接矩阵的图G有一个k顶点的团 其中v是k的二进制表示 二 P类与NP类语言 证明过程图采用邻接矩阵编码CLIQUE w v w v 0 1 w为邻接矩阵表示的图有一个k团 非确定性算法输入分解计算n和k O n2 非确定性选择O n 确定性验证O n4 K 3 1 4 6 j 0 非确定性算法for i 1 i n i m choice 0 1 猜想switch m case0 a i 0 break case1 a i 1 j break if j k thenreject 二 P类与NP类语言 接受该语言CLIQUE的非确定性算法 用非确定性选择指令选出包含k个顶点的候选顶点子集V 然后确定性地检查该子集是否是团问题的一个解 算法分为3个阶段 算法的第一阶段将输入串w v分解 并计算出n 以及用v表示的整数k 若输入不具有形式w v或 w 不是一个平方数就拒绝该输入 显而易见 第一阶段可在时间内完成 在算法的第二阶段中 非确定性地选择V的一个k元子集V V 算法的第三阶段是确定性地检查V 的团性质 若V 是一个团则接受输入 否则拒绝输入 这显然可以在时间内完成 因此 整个算法的时间复杂性为 三 多项式时间验证 1 什么是多项式时间验证 上述算法的时间复杂度主要取决于第三阶段的验证算法 若验证部分可在多项式时间内完成 则整个非确定性算法具有多项式时间复杂性 从而所识别的语言为NP语言 三 多项式时间验证 2 如何进行多项式时间验证 多项式时间可验证语言类VP定义 验证算法定义为两个自变量的算法A x y 其中x是待验证的输入串 y为称为 证据 的二进制串 如果对任意串x L 存在证据y A x y 1 A验证的语言L x 存在证据y 满足A x y 1 多项式时间可验证语言类VP L L 存在一个多项式时间验证算法A x y 使得对任意x x L当且仅当存在y y O x k且A x y 1 三 多项式时间验证 3 证明定理 VP NP证明VP NPL NP L VPNP VP例如 哈密顿回路问题 一个无向图G