image

前言與心得整理

由於第六週的內容牽扯到P=NP相關理論還有NP-Complete的證明.所以我把內容拆成兩個禮拜,希望能夠更仔細地來了解這個部分.

相關文章

第六週前半部分的課程內容:

###Intractable Problems

P類問題

接下來會介紹一些需要耗費相當多的時間(指的是處理時間超過指數時間(polynomial-time)的問題.

回過頭來先要定義如何指出圖靈機的時間限制:

T(n): 指的是輸入w長度為n的時候,該圖靈機一定會停止的

這時候就會帶出第一個名詞: P 也就是如何定義一個問題是屬於P類的問題 (Class P problem)

	Class P:  指的是在DTM(Deterministic Turing Machine)下,其T(n)= polynomial-time (指數時間)

關於”P類”問題的範例

DTM可以被來當成是否可以用DFA(Deterministic Finite Automata_來表示其狀態的TM(Turing Machine). 所以其實要尋找類似的範例其實不難,只是該問題必須要是在指數時間才能解決的,課堂上提供的範例如下:

  • 在CFG的 L(G) 給予一個字串w.判斷w in L(G)
    • 之前有提過要快的話,必須使用CYK演算法.然後其時間複雜度為O(n^3)

NP類問題

在介紹NP類問題前,雖然課堂上老師直接透過背包問題(Knapsack Problem)來引導NP類問題.不過我個人認為,還是需要簡單的瞭解一下`NP類問題`的定義:

	Class NP: 指在NTM(Nondeterministic Turing Machine)下,其T(n)為指數時間(polynomial-time)

沒有錯,P類問題與NP類問題最大的差異是TM讀入一個輸入的時候.其反應是唯一的(DFA)或是多重的(NFA). 接下來就可以將背包問題(Knapsack Problem)開始帶入:

什麼是背包問題(Knapsack Problem)

關於背包問題的定義,種類與範例.其實這一篇台師大的文章講得非常好.這裡僅僅簡單的帶過:

背包問題: 將一堆東西放進背包,每一件物品有它的重量與價值,透過有限制重量的背包來取得放入價值的最大化.

解法與時間複雜度: 對於背包問題的解法,一般而言就是透過動態規劃(Dynamic Programming)的方式來找.如此一來: 如果有n個物件,就必須要找出該物件放進背包與不放進背包的價值.所以時間複雜度為O(n * 2^n) (2是因為要計算 出現與不出現.必須要反覆計算n回)

P = NP ?

接下來就帶入大家都了解的P=NP這個被稱為史上七大難解問題之一. 究竟P是不是相同於NP? 其實課堂上也有一些簡單的討論.

取自Wiki,NP-Complete 概念

以上的圖是來是Wiki,主要是講解如果認為P不等於NP的時候.他的概念是以這樣的方式作為出發來討論.

NP-Complete Problem

首先要討論P是否相同於NP,可以透過一個面向來探討.就是透過NP完全(NP-Complete Problem).

A decision problem C is NP-complete if:

  • C is in NP, and
  • Every problem in NP is reducible to C in polynomial time

這是從NP-Completeness看到比較formal的定義.也就是說,如果我們能夠透過polytime reductions的方式來朝向證明NP-Completeness

Polytime Reductions

Polytime Reductions 又稱為Polynomial-time reduction,以下會解釋這種reduction 的目標與方法:

目標: 如果可以找到一個方式將所有的NP問題歸約(reduction)成語言L,並且能夠找到多項式的解決時間(Polytime).那麼就可以找到多項式的演算法(deterministic polytime algorithm)來計算所有的NP問題.

簡單的來說:

  • 只要能夠找到一個方式來將所有的NP -> (Polytime Reduction) L
  • 只要能夠找到Polytime Algorithm for L
  • 那麼就能夠推導出其他Deterministic Polytime Algorithm給所有的NP

方法:

  • 先定義有L與M兩種語言
  • L->(polytime reduction) M
  • Transducer
    • 先做Transducer將原本的資料由長度為n作轉換為x
    • 透過Transducer轉換的資料長度會大於n,但是會 <= p(n)
    • 將這系列動作既做 T(w) = x
  • 如果w是在L裡面,那麼透過這樣轉換出來的x 必定也在M裡面.

Proof that Polytime Reduction “Work”!!

要如何證明Polytime Reduction是有作用的.

  • 先定義有L與M兩種語言,其中:
    • L有輸入w其長度為n,M有輸入x
    • L有演算法p(n), M有演算法q(x)
  • L->(polytime reduction) M
  • 可以透過transducer轉換出 p(n)=x
  • 可以計算出M的演算法為q(x) = q(p(n))
  • 全部的時間相同 L的計算時間+M的計算時間 = p(n) + q(p(n))
  • 已經知道 p(n)為polytime 並且也知道 q(p(n))也為polytime
  • p(n) + q(p(n)) 也是 polynomial time

The Satisfiability Problem (SAT)

SAT是NP問題裡面的最常被提到的問題之一,而所謂的SAT就是給予一個運算式來(ex: (x+y)(-x + -y) ) 來尋找該式子為true的狀況,該x與y的組合. 這個範例裡面,解答為:

  • x=0; y=1
  • x=1; y=0

注意: SAT裡面的優先順序是 NOT(!)->AND(.)->OR(+)

講解Cook-Levin理論 (或稱為Cook’s Theorem)

講解Cook-Levin理論提供了一個方式來證明SAT是NP-Complete(NP完全問題).

個人很推薦這段兩分鐘的Youtube: Cook’s Theorem,裡面雖然沒有講解Cook’s Theorem的流程,但是把主要精神講解出來.(重點是他只有兩分鐘)

Cook’s Theroem 準則

,Cook–Levin理論提供了很不同的思路去解決SAT是NP-Complete的問題(不過人家也花了十一年).也就是透過演算法轉換的方式來證明這個問題是NP-Complete,而不是直接去證明這個問題是NP-Complete(from wiki)

  • 已知一個NP-Complete的問題必定存在一個Algorithm,可以在Polytime解決這個NP-Complete問題.
  • 如果能夠把任何演算法透過圖靈機轉換成 Boolean Formula(一個布林方程式是否存在解)
  • 那麼也就能證明這個問題是NP-Complete

NTM(Nondetermistic Turing Machine) for SAT

透過這樣的思路,完整定理是:

	讓L屬於NP,而M代表NTM(Nondeterministic Turing Machine).我們需要設計一個L,並且使得它的time-bond <= p(n) (其中n是輸入的個數),並且 p 是 polynomial.

關於詳細的證明流程,我還在仔細研究.目前看了好幾份slide跟課程都無法正常理解. 證明 NP-Complete 陷入了一個 各家slide 方向與準則相同… 但是沒有一家證明流程是一樣的 XDD

希望下周可以完成.

程式作業/Homework

下週再做Homework

相關程式

本週相關程式,是把NP問題中的PCP拿來當作練習的題目. 本來很好奇為何在網路上沒有找到比較好的解法. 仔細研究才發現PCP(Post’s Correspondence Problems)其實還沒有一個比較好的解法. 主要原因可能因為PCP本身有太多比較難以解決得部分,比如說:

  • 判定錯誤的停止條件. 由於PCP是NP問題,而且又是屬於Recursively enumerable language (根據我了解的定義) 所以它無法正確的知道,何時可以停止(halt)
  • 目前判斷了循環的一個case,根據我這星期研究PCP循環的case可能目前只發現兩個 (1) 解答循環 (2) 一方的長度無限制延長..

我的解法在這裡,https://github.com/kkdai/pcp 不是一個完整解法,但是持續研究如何解決.

參考網址


Evan

Attitude is everything