創新實訓個人記錄：P versus NP

• • computation&&computable&& computational ef?ciency
  • 一些符號
  • decision problem / language(決策問題)
  • 復雜性類別：P versus NP, NP-hard, NP-complete
  • • P
    • NP
    • NP-hard, NP-complete（NP難，NP完全）

computation&&computable&& computational ef?ciency

computation: 計算。以有限的步驟，從一組輸入得到一個輸出的過程；可以在各種物理和數學系統中進行，例如圖靈機，λ演算，元胞自動機；所有這些形式的計算都是等效的，即每個模型都能夠實現我們可以在任何其他模型上構想的所有計算
computable: 可計算的。不可計算的：對于某些輸入，沒有進入無限循環（即，永不停止）沒有電腦能解決這些問題。
quantify computational ef?ciency: 量化計算效率。
舉一個例子：兩數乘法。第一種是重復添加，計算a·b,只需要把a加上它自己b-1次。另一種方法是下圖所示的grade-school 算法。

我們通過學習，當我們增加輸入的大小時，基本操作規模的數量是怎么樣的，來量化一個算法的效率。我們設置，基本操作為一位的加法和乘法。（在其他設置中，我們也可以把除法設置為基本操作。）
輸入的大小是數字中占位的數量。用于兩個n位數乘法的基本操作的數量（即在$10^n?1$ 和 $10^n$之間的數字），用grade-school算法最多需要$2n^2$次（$n^2$次乘法，$n^2$次加法），用“重復加”算法至少需要$n10^{n?1}$次（a需要重復加自己b-1次，b是n位數，那么b是在$10^{n?1}$ 和 $10^n$之間的數字；通常，b-1≥$10^{n?1}$；又因為a是n位數，所以至少需要重復加$n10^{n?1}$次）。
可以看出，$2n^2$和$n10^{n?1}$根本不是一個量級的，效率高低也很明顯。這就是計算效率，它很重要，這本書也主要是圍繞計算效率來討論。

一些符號

• 如果$S$是一個有限集合，那么在$S$上的字符串是一個$S$中元素的有限有序元組，元組元素來自于$S$。在這本書中，我們通常考慮在二進制{$0,1$}上的字符串。
• 對于任何非負整數$n$，我們用$S^n$表示在$S$上長度為$n$的字符串的集合（$S^0$表示由空元組組成的單例）。我們用$S^{?}$表示所有字符串的集合（即$S^{?}={\cup }_{n\ge 0}{S}^n$，$S^{?}$是所有$S^n$的并）。
• 那么，{0, 1}${}^n$就是表示在{0, 1}上長度為$n$的有限有序元組的集合，其中元組元素來自于{0, 1}。
• 如果$x$和$y$是字符串，那么我們用$x?y$或者簡單一點，用$xy$來表示$x$和$y$的聯級（首先包含$x$的元素，然后是$y$的元素的元組）。如果$x$是一個字符串，而且$k\ge 1$是一個自然數，那么$x^k$表示$x$的$k$次復制的聯級。例如，$1^k$表示一個包含$k$個$1$的字符串。字符串$x$的長度用$|x|$表示。

decision problem / language(決策問題)

由于技術上的方便，本書重點考慮決策問題。什么是決策問題？
舉一個例子：The dinner party task（晚餐任務）。給定一個熟人清單，和他們之間不相處的對，找到你能邀請來聚會的最大熟人集合，保證每兩個被邀請者都能和另一個相處。
為了解決這個問題，我們把它放到圖里考慮。通過用圖的頂點表示可能的參加晚宴的被邀請者，該圖的頂點在任何兩個不相處的人之間都具有邊，則從介紹開始的晚宴計算問題就變成了尋找最大尺寸的獨立集（一組頂點）的問題。
$INDSET=<G,k>:?S?V(G)s.t.|S|\ge kand?u,v\in S,\overline{uv}\in /E(G)$
輸入INDSET，是否存在size≥k的獨立集，這是一個布爾問題，輸出只有一個位，0或1。

通過這個例子，我們可以知道決策問題大概是怎么樣的了。輸入一個問題，問題的答案只有“是”或“否”。用數學符號表示：如果機器計算函數$f_L$：{0，1}${}^{?}$→{0，1}，則機器會決定決策問題L?{0，1}${}^{?}$，其中$f_L（x）=1?x\in L$

復雜性類別：P versus NP, NP-hard, NP-complete

先介紹一個小概念：DTIME：Deterministic time，確定性時間。令T：N→N（N是自然數）為某種函數。 如果有一個圖靈機在時間c·T(n)中運行某個常數c>0并確定L，那么我們稱決策問題L在DTIME(T(n))中。我們討論的圖靈機更確切地來說是“確定性圖靈機”。

P

然后呢，我們嘗試使“高效計算”的概念更加精確。我們將其等同于多項式運行時間，這意味著對于某些常數c> 0，它最多為$n^c$。用數學符號表示：$P={\cup }_{c\ge 1}$ DTIME $(n^c)$. （P:polynomial）

兩個需要注意的點：

• P類只包含決策問題。我們可以問“INDSET in P?" ; 但是對于兩數乘法，我們不能問“整數乘法 in P?” ;而要問“整數乘法的決策版本 in P? ” ;用數學符號表示就是{<xy,i>: The ith bit of xy is equal to 1}
• 運行時間是輸入位數的函數（二進制 位數）

NP

與P對比，先引出概念。P類包含可以有效解決的決策問題；NP類包含可有效驗證其解決方案的問題集。

如果存在多項式$p：N\to N$和多項式時間TM $M$（稱為決策問題L的檢驗器）使得對于所有$x\in${0, 1}${}^{?}$，有$x\in L$?$?u\in${0, 1}${}^{p(|x|)}$ $s.t.M(x,u)=1$ 則決策問題L? {0, 1}${}^{?}$在NP中。($u$是對于$x$的certificate)
舉個例子：對于線性規劃$a_1{u}_1$ + $a_2{u}_2$ +··+ $a_n{u}_n$≤$b$，確定是否有滿足所有不等式的變量$u_1$，…，$u_n$有理數的賦值。certificate是賦值。

$P?NP$：顯然，因為多項式$p(|x|)$允許為0（換句話說，$u$可以是一個空字符串），所以$P?NP$。

NP-hard, NP-complete（NP難，NP完全）

如果可以在多項式時間內將所有NP問題歸約為問題X，則認為X是NP-Completeness；
如果可以在多項式時間內將所有NPC問題歸約為問題Y，則認為Y是NP-Hard；
如果同時在NP和NPH中，則該問題是NPC的。

NPC問題代表了NP中最困難的問題。 如果任何NPC問題具有多項式時間算法，則NP中的所有問題都可以。 NP完全問題集通常用NP-C或NPC表示。

NP-Hard問題不一定是NP問題，也不一定是決策問題。滿足所有NP問題可歸約到NPC，所有NPC可歸約到NPH。

總結

以上是生活随笔為你收集整理的创新实训个人记录：P versus NP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。