第四讲NP完全性理论

图灵机是计算机的一种简单数字模型，尽管简
单，但它具有模拟通用计算机的计算能力。为
算法和可计算性研究提供了形式化描述工具。
带（tape）
Finite control
图灵机的基本 模型
Xn B B ...
X1
X2
Xi
单元格（cell）

带符（tape symbol）
读写头在每一时刻扫描带上的一个单元
有限状态控制器 …… 1 0 B 1 0 1 1 0 0 B 0 1 1 0 0 1 B ……
带子可读可写 无限长的带子 读写头可左移右移
图灵机的工作机制
在一个图灵机的动作中，图灵机根据带头 （读写头）所扫描的符号和有限控制器的 状态可能作
改变状态
在被扫描的带单元上重新写一个符号，以代替 原来写在该单元上的符号. 将带头向左或者右移一个单元。
多项式与指数函数时间比较 Size n 10 .00001 second .0001 second .001 second .1 second .001 second .059 second 20 .00002 second .0004 second .008 second 3.2 second 1.0 second 58 minutes 30 .00003 second .0009 second .027 second 24.3 second 17.9 minutes 6.5 years 40 .00004 second .0016 second .064 second 1.7 minutes 12.7 days 3855 centuries 50 .00005 second .0025 second .125 second 5.2 minutes 35.7 years 2*108 centuries 60 .00006 second .0036 second .216 second 13.0 minutes 366 centuries 1.3 *1013 centuries
Definition
Any problem for which the answer is either zero or one is called a decision problem. An algorithm for a decision problem is termed a decision algorithm. Any problem that involves the identification of an optimal (either minimum or maximum) value of a given cost function is known as an optimization problem. An optimization algorithm is used to solve an optimization problem.
带有一个最左单元，向右则是无限的。 带的每个单元可容纳一个带符号
开始时，最左边n个单元装着输入（n>＝0，n为有限数），它是 一个字符串，符号都选自“带符号”的一个子集，即所谓的“输 入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊 的带符号，但不是输入符号。
图灵机（Turing Machine)
NP完全性理论
内容
计算的形式描述－－计算模型 可计算性理论 P类与NP类问题 NP完全性理论 NP完全性的典型例子
1 理论计算模型－图灵机
A.Turing在1936年介绍了这样一个通用的计算 模型，该模型具有以下两个性质
该模型的每个过程都是有穷可描述的； 过程必须是由离散的、可以机械执行的步骤组成。
Example 2 Sorting
要將 A[1:n] 中的元素作 non-decreasing 的排列，nondeterministic algorithm 如下
void Nsort(int A[], int n) { int B[SIZE], i, j; for(i=1;i <= n;i++) B[i] = 0;//初值化 for(i=1;i <= n;i++) { j = Choice(1, n);//選一個正確的位置 complexity if(B[j]) Failure();//確認B[j] Time 沒有被用過 O(n) B[j] = A[i]; } for(i = 1;i <= n-1;i++) if(B[i] > B[i+1]) Failure();//作確認 for(i=1;i <= n;i++) cout << B[i] << ‘ ‘; cout << endl; Success(); }
Non-deterministic satisfiability
void Eval(cnf E, int n){ int x[SIZE]; for(int i=1;i <= n;i++) x[i] = Choice(0, 1); if(E(x, n)) Success(); else Failure; } 這個演算法的 time complexity 是 O(n) 再加上 E(x, n) 的時間， 計算 propositional formula 值的時間與該 formula 的長度有關。 這是第一個被證明為 NP-complete 的問題。
NP问题：
在非确定型图灵机上多项式时间可解的问题 在确定型图灵机上多项式时间可验证的问题
P类包含于NP类中 NP类问题在确定图灵机上指数时间可解
非确定型图灵机和确定型图灵机的计算能力相当
Commonly believed relationship between P and NP
Is there an assignment of values 0 or 1 to variables so that the formula evaluates to 1?
Conjunctive Normal Form (CNF)
A clause is the OR of some literals A Boolean formula consisting of several clauses separated by AND is a CNF formula
E.g., (a+b+c)(b’+d+e’+f)(a’+e)
Satisfiability Problem
…contd
3-CNF: a CNF formula in which each clause has 3 literals
E.g., (a+b+c’)(d+e’+f)(a’+f’+g)
要如何來看待 non-deterministic algorithm 呢？ 可以用平行處理的角度來看，也就是當作同時有很多 很多機器一起作同一個問題，每個機器用不同的 choice 的結果來作，若有一個成功的話，其他的就 不用再作；若某個失敗、就自己停下來即可。 另外更好的解釋是，實際上可能有一種方法可以選擇 一個正確的答案出來(只要正確答案存在)，只是我們 還不曉得而已（上帝知道），Choice(S) 就代表可以 找到 S 中正確答案的函數(若正確答案存在)。若正確 答案不存在的話，Choice(S) 還是會找出一個答案， 所以我們需要確認此答案是否正確。
Given a 3-CNF formula, is it satisfiable?
That is, is there an assignment (to variables) that evaluates the formula to 1 This is also called the 3-CNF-SAT problem
我們定義下列三個涵數來說明這種算法。
Choice(S): 從 S 中選一個正確的答案來(若正確答案 存在的話)。 Failure(): 沒有成功地完成工作。 Success(): 成功地完成工作
這三個涵數的執行時間都是 O(1)。 只有在不可能有正確答案的情形下， nondeterministic algorithm 才無法成功地完成工 作。 一個可以執行 non-deterministic algorithm 的 機器稱為 non-deterministic machine.
Non-deterministic algorithms
目前所講的算法都有一個前提假設，就是它的每個 運算(operation)的結果都是獨一(確定)的。這種性 質的算法可以在實際的電腦上執行，稱為 deterministic algorithms. 在討論計算理論時，可以將這種限制拿掉，也就是 可以假設一個運算的結果不唯一，可能是某 n 個結 果中的一個，而且一定會是正確的那一個。這樣子 的算法稱為 non-deterministic algorithm。這種 算法無法在實際的電腦上執行。
With computer 1000 times faster 1000N1 31.6N2 10N3
n5
2n
N4
N5
2.5N4
N5 +6.64
3.98N4
N5 +9.97 N6 +6.29
3n
N6
N6 +4.19
指数灾难：计算量的指数增长
1200 1000 800 600 400 200 0 1 3 5 7 9 指数增 长 线性增 长
其他图灵机模型
“实际的”的图灵机模型
单带图灵机（1TM） 多带图灵机（kTM） 随机存取机（RAM）
“实际的”
单位时间内完成的工作量有一个多项式上界
所有“实际的”计算模型多项式时间等价
2 P类与NP类问题
算法的时间复杂度（分成二类）
多项式时间 指数时间
可计算与不可计算
q0 Q T B–T F Q
开始状态
特殊带符:空白符
终态集合
转移函数 : 可随机选择
P类 （Polynomial)
P类
具有多项式时间算法的判定问题形成的计算复杂 性类 在确定型图灵机上多项式时间可解的问题
NP类(Nondeterministic Polynomial )
P
NP
一般相信 P 與 NP 兩集合不相同，也就是相信有些問題是屬於 NP 而不屬於 P，但目前仍然無法證明。 Cook 曾問過一個問題：有沒有什麼問題應該屬於 NP 而不屬 於 P，如果該問題屬於 P 的話，就表示 P = NP 呢？
Satisfiability Problem
Given a Boolean formula (with variables and Boolean operators AND, OR and NOT), is it satisfiable?
Example 1 searching
A[1:n] 是一個 n 個元素的集合，要在 A 中搜尋一 個元素 x 的 non-deterministic algorithm 如下： int j = Choice(1, n); if (A[j] == x) {cout << j; Success();} cout << ‘0’; Failure(); 因為 Choice(1, n) 一定會找出一個正確的值，所 以拿它找出來的值 j 來比較 A[j] == x 若不成立的 話，就表示 x 不在 A 裡面。Time complexity 是 O(1)。
非确定型图灵机（NTM)
有限状态控制器 猜想模块
…… 1 0 B 1 0 1 1 0 0 B 0 1 1 0 0 1 B ……
猜想阶段 验证阶段
非确定型图灵机的形式化
形式定义 一个非确定型图灵机 TM 是一个七元组 M = (Q, T, , , q0 , B , F ).
有限状态集
有限输入符号集 有限带符号集 转移函数
Time complexity function
n n2 n3
n5
2n
3n
1小时能解决的最大规模
Time complexity function n
n2 n3
With present computer
N1 N2 N3
With computer 100 times faster
100N1 10N2 4.64N3
。
图灵机的形式化描述
形式定义 一个图灵机 TM (Turing machine) 是一个七元组 M = (Q, T, , , q0 , B , F ).
有限状态集
有限输入符号集 有限带符号集 转移函数
q0 Q T B–T F Q
开始状态
特殊带符:空白符
ຫໍສະໝຸດ Baidu
终态集合
转移函数 : Q Q { L,R }