清华大学：《算法分析与设计》（双语版） 第14讲 NP完全性理论介绍

内容提要 ·计算模型与计算复杂度关系 NP完全性理论介绍 ·问题分类:【P】与【NP】类 NP一难【hard】问题,NP完全集 清华大学 ·第一个NPC问题和NPC问题集 宋斌恒 ·如何证明一个问题是NPC问题 清华大学宋域恒 请华大学宋恒 引言 NPC问题 ·脑力劳动机械化【吴文俊先生】 ·P一NP一NPC问题定义及其猜想:NPC是 图灵机的停机问题:是否存在一个图灵机,他 类不可以在多项式时间内计算的问 可以回答其它图灵机是否停机【既算法是有界 题 的】 原则上是否存在一般数学问题的解题步骤的判 ·如果在量子计算模型中上述问题又如 决问题【希尔波特第十问题变种】 图灵公理:凡是可计算的函数都可以用一台图 灵机来计算 清华大学末斌恒 请华大学宋恒 下面介绍计算机械化的进程 明代数学家程大位著《算法统 宗》中关于珠算的插图 :a(m/ 清华大学末破恒 请华大学宋

1 清华大学 宋斌恒 1 NP完全性理论介绍 清华大学 宋斌恒 清华大学 宋斌恒 2 内容提要 • 计算模型与计算复杂度关系 • 问题分类：【P】与【NP】类 • NP－难【hard】问题，NP完全集 • 第一个NPC问题和NPC问题集 • 如何证明一个问题是NPC问题 清华大学 宋斌恒 3 引言 • 脑力劳动机械化【吴文俊先生】 • 图灵机的停机问题：是否存在一个图灵机，他 可以回答其它图灵机是否停机【既算法是有界 的】 • 原则上是否存在一般数学问题的解题步骤的判 决问题【希尔波特第十问题变种】 • 图灵公理：凡是可计算的函数都可以用一台图 灵机来计算 清华大学 宋斌恒 4 NPC问题 • P－NP－NPC问题定义及其猜想：NPC是 一类不可以在多项式时间内计算的问 题。 • 如果在量子计算模型中上述问题又如 何？ 清华大学 宋斌恒 5 下面介绍计算机械化的进程 清华大学 宋斌恒 6 明代数学家程大位著《算法统 宗》中关于珠算的插图

机械式手动计算机 机械计算机 ·法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机,并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统,其中一小轮转十个数字,下一个小 轮便转动一个数字,通过齿轮系的联 动,可以进行加法和减法的运算 清华大学宋域恒 请华大学宋恒 图灵 图灵机模型 大半个世纪以来,数学家、计算机 有限状态 控制器 念英国数学家Iuri 912-1954)而设立的图灵奖成为计 读写头 带 清华大学末斌恒 请华大学宋恒 图灵机模型 图灵机定义 图灵机模型用一个无限长的带子作为无限存储 图灵机是一个7元组(Q,T,6,q0,q1,q2, 它还有一个读写头,这个读写头能在带子上读 其中Q,∑,都是有穷集合并宜 写和移动:开始时,带子上只有输入串,其它地 1)Q是状态集 方都是空的当它需要保存信息时,读写头就把 2)∑是输入字母表不包括特殊空白符号 信息写在带子上为了读某个输入或写下的信 ·3)r是带字母表,其中:∈T,∑是的子 息,带子可能将读写头往回移动到这个信息所 在的地方这样读,写和移动,机器不停的计算 4)6:Q×r→Q×r×{LR}是转移函数 直到产生输出为止机器实现设置了两种状态 0∈Q是起始状态 接受或拒绝 6)q1∈Q是接受状 7)q2∈Q是拒绝状态,且q2≠q1 清华大学末破恒 请华大学宋

2 清华大学 宋斌恒 7 机械式手动计算机 清华大学 宋斌恒 8 机械计算机 • 法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机，并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统，其中一小轮转十个数字，下一个小 轮便转动一个数字，通过齿轮系的联 动，可以进行加法和减法的运算. 清华大学 宋斌恒 9 图灵 • 大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖. 清华大学 宋斌恒 10 图灵机模型 清华大学 宋斌恒 11 图灵机模型 • 图灵机模型用一个无限长的带子作为无限存储 , 它还有一个读写头 ,这个读写头能在带子上读 , 写和移动 : 开始时 ,带子上只有输入串 ,其它地 方都是空的 .当它需要保存信息时 ,读写头就把 信息写在带子上 .为了读某个输入或写下的信 息 ,带子可能将读写头往回移动到这个信息所 在的地方 .这样读 ,写和移动 ,机器不停的计算 , 直到产生输出为止 .机器实现设置了两种状态 : 接受 或 拒绝 清华大学 宋斌恒 12 图灵机定义 • 一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 • 1) Q 是状态集. • 2) ∑是输入字母表,不包括特殊空白符号︺. • 3) Γ 是带字母表,其中: ︺∈Γ,∑是Γ的子 集. • 4) δ: Q×Γ→Q×Γ×{L,R}是转移函数. • 5) q0∈Q是起始状态. • 6) q1∈Q是接受状态. • 7) q2∈Q是拒绝状态,且 q2≠q1

多带图灵机 非确定性的图灵机 ·在计算的任何时刻机器可以在多种可能 灵机相似,M 性中选择一种继续进行【永远选择正确 只是有多 的,可以理解为全部分支都计算完后选 个带子每 出正确的】它的计算是一课树,不同的分 个带子都 枝对应着机器不同的可能性如果某个计 有自己的 算分枝导致接受状态,则接受该输入.与多 读写头,用 带图灵机相同的是,它的计算能力与普通 于读和写 图灵机也是一样的当然他的计算速度就 不一样了 清华大学宋域恒 请华大学宋恒 现代计算机模型 随机存取机RAM CPU 类似现代计算机,有一个只读输入 运算器控制器出 只写输出带、指令计数器、内存储器 其零号寄存器用作累加器,内存不能 存储器 写,每个内存可以存放任意大的整数 有12条指令:load、 store、add、su mult、div、read、 write、jump、jgtz 外存设备 Izero、halt 清华大学末斌恒 请华大学宋恒 练习 随机存取存储程序机RASP ·利用RAM设计一个计算多项式函数求值 ·除了程序可以存储在存储器中并可以修 的程序:其中多项式为,变 改,其它与RAM都一样 量为 ·考虑问题:程序是什么?输入是什么? 复杂度是多少? 清华大学末域恒 请华大学宋

3 清华大学 宋斌恒 13 多带图灵机, • 和普通图 灵机相似, 只是有多 个带子,每 个带子都 有自己的 读写头,用 于读和写. 如图 清华大学 宋斌恒 14 非确定性的图灵机 • 在计算的任何时刻,机器可以在多种可能 性中选择一种继续进行【永远选择正确 的，可以理解为全部分支都计算完后选 出正确的】.它的计算是一课树,不同的分 枝对应着机器不同的可能性.如果某个计 算分枝导致接受状态,则接受该输入.与多 带图灵机相同的是,它的计算能力与普通 图灵机也是一样的.当然他的计算速度就 不一样了。 清华大学 宋斌恒 15 现代计算机模型 清华大学 宋斌恒 16 随机存取机RAM • 类似现代计算机，有一个只读输入带、 只写输出带、指令计数器、内存储器、 其零号寄存器用作累加器，内存不能 写，每个内存可以存放任意大的整数。 有12条指令：load、store、add、sub、 mult、div、read、write、jump、jgtz、 jzero、halt。 清华大学 宋斌恒 17 练习 • 利用RAM设计一个计算多项式函数求值 的程序：其中多项式为，变 量为x。 • 考虑问题：程序是什么？输入是什么？ 复杂度是多少？ 清华大学 宋斌恒 18 随机存取存储程序机RASP • 除了程序可以存储在存储器中并可以修 改，其它与RAM都一样

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 Σ∗

Operations on language 多项式时间内可求解问题 Union and intersection: same as the set 多项式时间内可求解的问题的特点 perations 多项式时间可求解的问题被认为是易处理 Complement ofL:I=2'-L Concatenation of two language L, and L2 理由1:尽管θ(n10)算法被认为是不 L={x1x2:x∈L1,x2∈L2} 易处理的,但事实上还没有什么实际问题有 如此之高的多项式算法。 Closure or Kleene Star 经验证明一但一个问题有多项式解,那 L*=GULULZULU 么常常会有更加有效的解决方案 清华大学宋域恒 请华大学宋恒 理由2:在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法 2抽象问题 例如:一个问题在串行随机存取机上有 多项式算法,则在图林机上亦有多项式算 抽象问题Q是集合I和S上的二元关系。其中 法,在并行机上亦如此。 理由3:多项式算法时间问题集合有非常好的 ·例如:①最短路径问题:问题实例(G, 封闭性质,它在加、乘、复合运算下都是 u、v):一个圆和其上两个顶点;问题解 封闭的 是(u~v)一个从u到v的由边相连的顶点 【本课程研究的算法大部分是多项式的,研 究的问题也是在多项式时间内可解的,对 ②查找最小值问题:问题实例 于不能在多项式时间内求解的问题该如何 a1,…,an>一个数组。解:数m。 处理?】 清华大学末斌恒 请华大学宋恒 判决问题 3.编码:抽象对象集合S的编码是: 抽象对象集合S的编码是 · Decision问题:如果I={0,1}或 E:S→∑*即把S中的对象e转化成一个二进 yes,no},则称问题是判决问 制(可以是多进制)的串。 题,下面我们只关心判决问题。 优化问题一般都可以转换成判决 构成,称其为具体问题。我们称 辈漆 问题。 在0(T(n))时间内解决了一个具体问 题,如果此问题i的长度|i是n,此算法可 在0(T(n))时间内求解此问题 一个抽象问题可以编码成具体问题。 清华大学末破恒 请华大学宋

5 清华大学 宋斌恒 25 Operations on language • Union and intersection: same as the set operations • Complement of L: • Concatenation of two language L1 and L2: • Closure or Kleene Star: – L*={ε}U L U L2 U L3 U… L = Σ − L * { : , } 1 2 1 1 2 L2 L = x x x ∈ L x ∈ 清华大学 宋斌恒 26 多项式时间内可求解问题 • 多项式时间内可求解的问题的特点 – 多项式时间可求解的问题被认为是易处理 的，有三条理由： 理由1：尽管Θ(n100)算法被认为是不 易处理的，但事实上还没有什么实际问题有 如此之高的多项式算法。 经验证明一但一个问题有多项式解，那 么常常会有更加有效的解决方案。 清华大学 宋斌恒 27 理由2：在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法。 例如：一个问题在串行随机存取机上有 多项式算法，则在图林机上亦有多项式算 法，在并行机上亦如此。 理由3：多项式算法时间问题集合有非常好的 封闭性质，它在加、乘、复合运算下都是 封闭的 【本课程研究的算法大部分是多项式的，研 究的问题也是在多项式时间内可解的，对 于不能在多项式时间内求解的问题该如何 处理？】 清华大学 宋斌恒 28 2.抽象问题： 抽象问题Q是集合I和S上的二元关系。其中 I是问题实例集合，S是问题解集合。 • 例如：①最短路径问题：问题实例（G， u、v):一个圆和其上两个顶点；问题解 是（u～v)一个从u到v的由边相连的顶点 集。 ②查找最小值问题：问题实例： ＜a1,…,an＞一个数组。解:数m。 清华大学 宋斌恒 29 判决问题 • Decision问题：如果I＝｛0，1｝或 ｛yes,no｝，则称问题是判决问 题，下面我们只关心判决问题。 优化问题一般都可以转换成判决 问题。 清华大学 宋斌恒 30 3.编码：抽象对象集合S的编码是： 抽象对象集合S的编码是： E：S→∑＊即把S中的对象e转化成一个二进 制（可以是多进制）的串。 如果一个问题的实例是由二进制串集 构成，称其为具体问题。我们称一个算法 在O（T（n)）时间内解决了一个具体问 题，如果此问题i的长度|i|是n，此算法可 在O（T（n)）时间内求解此问题。 一个抽象问题可以编码成具体问题

Problem vs. language Polynomial time a decision problem Q can be regarded as a polynomial time by an algorithm A if A anguage L accepts every binary string in L in polynomial L={x∈Σ:Q(x=1} time无法保证非L中的语言在多项式时间内 被拒绝] A language accepted by an algorithm a is L={x∈{0,1}:A(x=1 We say that a language is decided in polynomial time by an algorithm a if A A language decided by an algorithm A if it ccepts every binary string in L in polynomial accepts all string x with A(x)=I and rejected time, and rejects in polynomial time the string all string x with A(x=0 not in L 清华大学宋域恒 请华大学宋恒 class p的另一个等价定义 Polynomial time verifications P=(Lc 10, 11*: there exists an algorithm A Verification algorithm a is a two arguments that decides L in polynomial time) algorithm where one argument is an nd the other binary string y called a certificate A two arguments algorithm A verify input x if there exists a certificate y 清华大学末斌恒 请华大学宋恒 Language defined by verification NP的一个等价定义 L=(x in (0, 1): there exists y in (0, 1) A language L belongs to NP if and only if such that A(x, y)1g here exists a two-input polynomial-time algorithm A and a constant c such that L=(x in ( 0, 1;": there exists y in (0, 1)with lyO(xl)such that A(x, yl We say that algorithm A verifies language L 清华大学末破恒 请华大学宋 6

6 清华大学 宋斌恒 31 Problem vs. language • A decision problem Q can be regarded as a language L: – L={x∈Σ∗ : Q(x)=1} • A language accepted by an algorithm A is – L={x∈{0,1}∗ : A(x)=1} • A language decided by an algorithm A if it accepts all string x with A(x)=1 and rejected all string x with A(x)=0 清华大学 宋斌恒 32 Polynomial time • We say that a language is accepted in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time[无法保证非L中的语言在多项式时间内 被拒绝] • We say that a language is decided in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time, and rejects in polynomial time the string not in L 清华大学 宋斌恒 33 class P的另一个等价定义 • P={L ⊆ {0,1}*: there exists an algorithm A that decides L in polynomial time} 清华大学 宋斌恒 34 Polynomial time verifications • Verification algorithm A is a two arguments algorithm where one argument is an ordinary input string x and the other is a binary string y called a certificate. • A two arguments algorithm A verify an input x if there exists a certificate y such that A(x,y)=1. 清华大学 宋斌恒 35 Language defined by verification • L={x in {0,1}*: there exists y in {0,1}* such that A(x,y)=1} 清华大学 宋斌恒 36 NP的一个等价定义 • A language L belongs to NP if and only if there exists a two-input polynomial-time algorithm A and a constant c such that • L={x in {0,1}*: there exists y in {0,1}* with |y|=O(|x|c ) such that A(x,y)=1} • We say that algorithm A verifies language L in polynomial time

NP两种定义是等价的 关于团问题属于NP的两种表述 用非确定性图灵机和验证算 类的 ·团:给定无向图和整数k,确定是否存在一个 定义是等价的 包含k顶点的完全子图【团】【 Clique】。 ·非确定图灵机算法:一个转移函数:给定k 可以不确定地转移到任意一个包含k个顶点的 图,然后确认该子图是否是团。其复杂度为 多项式 ·验证算法:给定一个k阶子图,验证它是否为 清华大学宋域恒 请华大学宋恒 CO-NP P is a subset of np of L in NPi P=NP=CO-NP NP=CO-NP 余集 P CO-NP NP 清华大学末斌恒 请华大学宋恒 The most possible cases NP-Complete and reducibility The"hardest"language in NP, with 多项式约简: we call Li is polynomial NP nCo-NP)NP- time reducible to L, denoted as L, s, L, if there exists a polynomial-time function f: 10, 1*210, 1)*such that for all x in 10, 1*, x in Li iff f(x)in Ly 清华大学末破恒 请华大学宋

7 清华大学 宋斌恒 37 NP两种定义是等价的 • 用非确定性图灵机和验证算法给NP类的 定义是等价的 清华大学 宋斌恒 38 关于团问题属于NP的两种表述 • 团：给定无向图和整数k，确定是否存在一个 包含k顶点的完全子图【团】【Clique】。 • 非确定图灵机算法：一个转移函数：给定k， 可以不确定地转移到任意一个包含k个顶点的 子图，然后确认该子图是否是团。其复杂度为 多项式。 • 验证算法：给定一个k阶子图，验证它是否为 团。 清华大学 宋斌恒 39 co-NP • Complexity Class co-NP={L: complement of L in NP} • 余集 清华大学 宋斌恒 40 P is a subset of NP P=NP=co-NP NP=co-NP P Co-NP NP ∩co-NP NP =P 清华大学 宋斌恒 41 The most possible cases Co-NP NP ∩co-NP NP P 清华大学 宋斌恒 42 NP-Complete and reducibility • The “hardest” language in NP, with polynomial-time reducibility. • 多项式约简：we call L1 is polynomial￾time reducible to L2, denoted as L1 ≤p L2, if there exists a polynomial-time function f: {0,1}* Æ {0,1}* such that for all x in {0,1}*, x in L1 iff f(x) in L2

Class NPC Existence of NPC problem NPC=(L in NP: L'S, L for every L' in NP) Circuit satisfiability:【芯片满足性问题】 NP-Hard: ifL's L for every L' in NP,we Input n Boolean variables after a sequence of call L is NP-hard Boolean operations it outputs a value from Theorem344 If any one of the NPC f0, 11, if there exists a input such that its output say the circuit is satisfiable problem is belong to P, then P=NP Circuit-SAT=( C is satisfiable boolean Theorem Circuit-SAT is belong to npc 清华大学宋域恒 请华大学宋恒 NP-completeness proofs Lemma34. 8 证明 circuit-satisfiability问题是NPC问 ·如果L是一个语言,如果存在一个L属于 题,依赖我们是否能够证明对于所有属 NPC,且满足L’≤L,则L是NP一难的 于NP的语言L都有:L≤ Circuit-SAT,其 ( NP-hard),如果进一步有L是NP则L属 证明超出了我们的课程的内容。 于NPC ·那么对于一般问题的NP完全是如何证明 ·证明:利用定义可以证明 的?这里我们把其中的过程做个介绍: 清华大学末斌恒 请华大学宋恒 般证明语言L是NPC的步骤 Formula satisfiability ·证明L属于NP Language SAT is defined as ·选取一个已知的NPC语言L SAT的实例是一个逻辑公式中,其构成如下 ·找到一个算法f使得f将L的每一个属于 1.n布尔变量:x1x2x3x 0,1}*实例x映射到L的实例fx) 2.m布尔运算符:and、or、not、 mplication、 if and only if(-,∧,V,→),)和 证明函数满足x属于L等价于f(x)属于 3.括号(没有多余括号) L对于所有属于{0,1}*的x都成立 我们可以证明SAT属于NPC【Cook定 ·证明计算f的算法是多项式的 理】 清华大学末域恒 请华大学宋

8 清华大学 宋斌恒 43 Class NPC • NPC={L in NP: L’ ≤p L for every L’ in NP} • NP-Hard: if L’ ≤p L for every L’ in NP, we call L is NP-hard • Theorem34.4 If any one of the NPC problem is belong to P, then P=NP 清华大学 宋斌恒 44 Existence of NPC problem • Circuit satisfiability:【芯片满足性问题】 – Input n Boolean variables after a sequence of Boolean operations it outputs a value from {0,1}, if there exists a input such that its output is one we say the circuit is satisfiable. • Circuit-SAT={:C is satisfiable boolean combinational circuit} • Theorem Circuit-SAT is belong to NPC 清华大学 宋斌恒 45 NP-completeness proofs • 证明 circuit-satisfiability 问题是NPC问 题，依赖我们是否能够证明对于所有属 于NP的语言L都有： L ≤p Circuit-SAT, 其 证明超出了我们的课程的内容。 • 那么对于一般问题的NP完全是如何证明 的？这里我们把其中的过程做个介绍： 清华大学 宋斌恒 46 Lemma34.8 • 如果L是一个语言，如果存在一个L’属于 NPC，且满足 L’ ≤p L，则 L是NP－难的 （NP-hard）,如果进一步有L是NP则L属 于NPC。 • 证明：利用定义可以证明 清华大学 宋斌恒 47 一般证明语言L是NPC的步骤 • 证明L属于NP • 选取一个已知的NPC语言L’ • 找到一个算法f使得f将L’的每一个 属于 {0,1}*实例x映射到 L的实例 f(x). • 证明函数f满足 x 属于 L’ 等价于 f(x) 属于 L对于所有 属于{0,1}*的x都成立 • 证明计算f的算法是多项式的 清华大学 宋斌恒 48 Formula satisfiability • Language SAT is defined as: – SAT的实例是一个逻辑公式φ，其构成如下 1. n布尔变量：x1,x2,x3,…xn. 2. m布尔运算符：and、or、not、 implication、if and only if(¬,∧,∨,→,↔)和 3. 括号（没有多余括号） ¾ 我们可以证明SAT属于NPC【Cook定 理】

证明:SAT属于NP 3-CNF-SAT ·只需要证明把一个实例代入公式进行布 Formula in conjunctive normal form 尔运算即可,其复杂度是多项式没有任 何问题! f(clause)A(clause, )A.A(clause) ·【有优先级的公式计算问题是多项式 Where clauses contains only - v and 的】 variables(variables and - -variables called SAT是NP-hard的:我们可以把 Circuit literals Satisfiable问题约简为SAT问题,而后证 3-conjunctive-normal-form: every clause 明约简过程是多项式的和充要的 contains exactly 3 liter 清华大学宋域恒 请华大学宋恒 3- CNF-SAT是NP完全的 The Clique Problem 验证是多项式的,没有问题 Clique Problem (Hi): A clique is a complete subgraph of G. Here above G is a graph CLIQUE=( G is a graph with a Theorem: Clique problem is NP-complete 清华大学末斌恒 请华大学宋恒 Vertex-Co Hamiltonian-cycle A vertex-cover of an undirected graph G=(V, E)is A Hamiltonian cycle is a sequence of v a subset V contains in V such that if (u, v)in E such that it runs all the vertices once exactly then u in V or v in V(or both). excepting the start and end vertex is the A vertex-cover problem is to find a vertex cover same one(it runs two times), and the of m size in a given graph running sequence is a path of the graph ecision problem: VERTEX-COVER=(<G, k: G as a vertex cover of size k) HAM-CYCLE is belong to npc · VERTEX-COVER属于NPC 清华大学末破恒 请华大学宋

9 清华大学 宋斌恒 49 证明：SAT属于NP • 只需要证明把一个实例代入公式进行布 尔运算即可，其复杂度是多项式没有任 何问题！ • 【有优先级的公式计算问题是多项式 的】 • SAT是NP－hard的：我们可以把Circuit－ Satisfiable问题约简为SAT问题，而后证 明约简过程是多项式的和充要的 清华大学 宋斌恒 50 3－CNF－SAT • Formula in conjunctive normal form: ¬∧∨→↔ • f= (clause1) ∧ (clause2) ∧ …∧ (clausek) – Where clauses contains only ¬, ∨ and variables(variables and ¬variables called literials) • 3-conjunctive-normal-form: every clause contains exactly 3 literals. 清华大学 宋斌恒 51 3-CNF-SAT是NP完全的 • 验证是多项式的，没有问题 清华大学 宋斌恒 52 The Clique Problem • Clique Problem（团）：A clique is a complete subgraph of G. Here above G is a graph. • CLIQUE={:G is a graph with a clique of size k} • Theorem: Clique problem is NP-complete 清华大学 宋斌恒 53 Vertex-Cover problem • A vertex-cover of an undirected graph G=(V,E) is a subset V’ contains in V such that if (u,v) in E, then u in V’ or v in V’(or both). • A vertex-cover problem is to find a vertex cover of minimum size in a given graph • Decision problem: VERTEX-COVER={:G has a vertex cover of size k} • VERTEX-COVER 属于 NPC 清华大学 宋斌恒 54 Hamiltonian-cycle • A Hamiltonian cycle is a sequence of V such that it runs all the vertices once exactly excepting the start and end vertex is the same one(it runs two times), and the running sequence is a path of the graph. • HAM-CYCLE is belong to NPC

Traveling-salesman Problem The subset-sum problem ·旅行商问题:旅行商必须访问所有n个城 problem, we are given a 市,而每两个城市之间的的行走费用不 finite set S subset of N, and a target t in n 同,求一条费用最小的路径 we ask whether there is a subset s subset of TSP iS NP-complete S whose elements sum to t SUBSET-SUM=(0 such scheme is a(1+e)-approximation algorithm Polynomial time approximation scheme Fully polynomial time approximation scheme 清华大学末域恒 请华大学宋

10 清华大学 宋斌恒 55 Traveling-salesman Problem • 旅行商问题：旅行商必须访问所有n个城 市，而每两个城市之间的的行走费用不 同，求一条费用最小的路径 • TSP is NP-complete 清华大学 宋斌恒 56 The subset-sum problem • In the subset-sum problem, we are given a finite set S subset of N, and a target t in N, we ask whether there is a subset S’ subset of S whose elements sum to t. • SUBSET-SUM={,there exists a subset S’ of S such that t = Σs∈S’ s} • SUBSET-SUM is NP-complete. 清华大学 宋斌恒 57 目前对NPC问题的处理 • 由于没有迹象表明NPC问题可以有多项 式时间的算法，当然也没有证明它没 有。目前人们对于NPC问题主要是采取 近似计算方法来解决这类问题， 清华大学 宋斌恒 58 Approximation Algorithms • Optimization problem has a minimum or maximum value(we assume it is positive), we denote as C • Approximation algorithm cannot get the optimal solution hence it computes an approximate value, called C*, • Performance ratios for approximation algorithms: ρ(n) satisfies • Max{C/C*, C*/C}≤ ρ(n) • We call the algorithm is ρ(n)-approximation algorithm 清华大学 宋斌恒 59 Approximation scheme • An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but also a value ε >0 such that for any fixed ε, the scheme is a (1+ε)-approximation algorithm • Polynomial time approximation scheme • Fully polynomial time approximation scheme 清华大学 宋斌恒 60