RAM、RASP复杂度耗费标准 图灵机模型与RAM模型计算能力 和复杂性关系 ·均匀耗费:不论计数器内整数多长,其 ·定理一、上述计算模型的计算能力等 读写、运算耗费均相等 价:既能够用图灵机计算的问题一定能 对数耗费:耗费与其二进制表示的位数 够用RAM计算,反之亦然。 成正比:既与数字大小的对数成正比 ·定理二、在对数耗费标准下、图灵机与 RAM的计算复杂度可在多项式时间内相 互归约。 清华大学宋域恒 请华大学宋恒 问题变换与复杂性归约 说明 利用变换和归约可以把一个问题的复杂 A∝nB:是指在完成问题A到B 性归结到另一个问题的复杂性 的转换过程中的转换过程需要Or(n) 问题A变换到问题B是指 将问题A的输入变换为问题B的适当输入 通常n表示问题A的规模,如果 求解问题B 把问题B的输出变换为问题A的正确解 r(m)是多项式,则称问题A可在多项 式时间内变换为问题B 清华大学末斌恒 请华大学宋恒 P、NP类定义 A Formal-language framework ·P={L是一个能够在多项式时间内被 形式化语言框架的一些概念简介 台确定性图灵机所接受的语言 Alphabet 2: is a finite set of symbols ·NP={LL是一个能够在多项式时间内被 一台非确定性图灵机所接受的语言} of symbols from 2. If 2=10, 11, then ·遗留概念说明 L=(10, 11, 101, 111, 1011,.., is the language of 语言 口 E is the empty string 语言与图灵机【算法与图灵机】 a2=E, 0, 1,00,01, 11,-.i is the set of all strings 为什么选择多项式 Every language is an element of x 清华大学末破恒 请华大学宋4 清华大学 宋斌恒 19 RAM、RASP复杂度耗费标准 • 均匀耗费：不论计数器内整数多长，其 读写、运算耗费均相等 • 对数耗费：耗费与其二进制表示的位数 成正比：既与数字大小的对数成正比 清华大学 宋斌恒 20 图灵机模型与RAM模型计算能力 和复杂性关系 • 定理一、上述计算模型的计算能力等 价：既能够用图灵机计算的问题一定能 够用RAM计算，反之亦然。 • 定理二、在对数耗费标准下、图灵机与 RAM的计算复杂度可在多项式时间内相 互归约。 清华大学 宋斌恒 21 问题变换与复杂性归约 • 利用变换和归约可以把一个问题的复杂 性归结到另一个问题的复杂性 • 问题A变换到问题B是指： – 将问题A的输入变换为问题B的适当输入 – 求解问题B – 把问题B的输出变换为问题A的正确解 清华大学 宋斌恒 22 说明 A∝τ (n) B：是指在完成问题 A 到 B 的转换过程中的转换过程需要O(τ (n)) 时间。 通常 n 表示问题 A 的规模，如果 τ (n) 是多项式，则称问题 A 可在多项 式时间内变换为问题 B 清华大学 宋斌恒 23 P、NP类定义 • P＝{L|L是一个能够在多项式时间内被一 台确定性图灵机所接受的语言} • NP＝{L|L是一个能够在多项式时间内被 一台非确定性图灵机所接受的语言} • 遗留概念说明： – 语言 – 语言与图灵机【算法与图灵机】 – 为什么选择多项式 清华大学 宋斌恒 24 A Formal-language framework • 形式化语言框架的一些概念简介： – Alphabet Σ: is a finite set of symbols – A language L over Σ is any set of string made up of symbols from Σ. If Σ = {0,1}, then L={10,11,101,111,1011,…} is the language of binary representations of prime numbers, ￾ ε is the empty string. ￾ Σ*={ε,0,1,00,01,11,…} is the set of all strings – Every language is an element of Σ∗