名詞整理

Top-down

由粗略的架構開始分析,逐步具體化,追溯出問題的細目。以生物分類法為例,其分類的層次由上往下依序為界門綱目科屬種,由粗略到清晰,此即是Top-down。

簡單來說,就是立下大綱後,再研究細節。

Top-down用在演算法設計時則是指:從問題本身開始,追溯相關細節以釐清答案。

Bottom-up

從基礎的條理開始綜合,逐步抽象化,建構起問題的綱要。以數學理論的推導過程為例,由簡單的基本假設,推論出高深的理論,此即是Bottom-up。

簡單來說,就是確定細節後,再整理大綱。

Bottom-up用在演算法設計時則是指:累積並整理已知的資訊,推論出問題的答案。

Inductive Method

「歸納法」,一件一件的聚集很多知識後,可以推導出一個結論。例如我們若知道「得A肝人生是黑白的」、「得B肝人生是黑白的」、「肝指數高人生是黑白的」、……,我們可以歸納出「肝若不好人生是黑白的」。

Deductive Method

「演譯法」,由一個龐大的事物,可以推導出一件一件的知識。例如我們若知道「肝若不好人生是黑白的」,就可以演譯出「得A肝人生是黑白的」、「得B肝人生是黑白的」、「肝指數高人生是黑白的」、……。

P & NP

示意圖

P問題

用多項式時間演算法就可以算出答案的問題。由於P問題也可以用指數時間演算法算得答案,故P問題也都屬於NP問題。

「找出一群數字當中最大的數字」是P問題。

註:P的全名是Polynomial time。通常以「P」來表示所有P問題所構成的集合。

NP問題

用指數時間演算法可以算出答案的問題,同時,只要給定了一個可能的答案,就可以用多項式時間演算法驗證該答案正不正確的問題。

「找出一張圖的一條Hamilton Path」是NP問題。
  當有一條可能的路線,照著路線走看看──它即是一個能驗證答案的多項式時間演算法。
「找出一張圖成本最小的Hamilton Path」不是NP問題。
  就算有一條可能的路線,還是必須要窮舉所有路線一一驗證之後,才知道哪條路線成本最少。
  所有路線共有指數次方條,是不可能用多項式時間演算法來驗證答案的。

值得一提的是,每一個NP問題,都可以設計出多項式時間演算法,轉換成另一個NP問題。換句話說,所有NP問題都可以用多項式時間演算法彼此轉換。

註:NP的全名是Non-deterministic Polynomial time。它的定義頗複雜,此處省略之。通常以「NP」來表示所有NP問題所構成的集合。

NP-complete問題

NP-complete問題是所有NP問題當中,是最具代表性、層次最高、最難的問題。NP-complete問題的各種特例,涵蓋了所有NP問題,只要解決了NP-complete問題,就有辦法解決每個NP問題。

另外,各個NP-complete問題都等價、都一樣難,彼此之間可以用多項式時間演算法互相轉換。科學家現今已經找出上百個NP-complete問題了。

「判斷一張圖是否存在Hamilton Path」已被證明是NP-Complete問題。

Complete的意義為:能夠代表整個集合的子集合。舉例來說,它就像是一個線性空間(linear space)的基底(basis)。

NP-hard問題

用多項式時間把NP問題進行一般化所得到的問題,同時,必須至少是比NP-complete問題還要難的問題。NP-hard問題有可能是:甲、NP-complete問題(是NP問題),乙、超出NP問題的複雜度,是更難的問題(脫離NP問題的範疇了)。

「找出一張圖成本最小的Hamilton Path」是NP-hard問題。
  它可以由「找出一張圖的一條Hamilton Path」這個NP問題,
  用多項式時間把每條邊加上成本而得。
  而且「找出一張圖成本最小的Hamilton Path」至少比NP-complete問題還難。

P = NP ?

這是資訊科學界的一個懸案。大意是說:到底NP問題能不能用多項式時間演算法解決呢?如果可以的話,那麼NP問題就都變成了P問題了。這意味著有一些花上幾十年幾百年算不出答案的問題,變得可以在幾分幾秒內計算完畢、得到答案。

有一個解決這個懸案的方向是:嘗試發明一個多項式時間演算法,來解決某一個NP-complete問題。一旦找到了一個多項式時間演算法能夠算出某一個NP-complete問題的答案,我們可以將此NP-Complete問題進行特例化得到所有NP問題,如此一來,所有NP問題就一定可以用多項式時間演算法算出答案了。