白話 NP

驗證容易搜尋難的問題

這篇講義用很不精確, 很不科學的方式解釋何謂 Non-deterministic Polynomial time problems (NP 問題)。 目的是給讀者一點直覺; 如果要看嚴謹的定義, 還是應該找一本演算法課本來讀。

有一類的問題長得像這樣: 「請找出一組 ... 滿足 ... 條件」 例如:

  1. Hamiltonian Cycle: 給你一個 graph, 請用一筆畫繞一圈將每個 vertex 走過恰好一遍, 並回到起點。 (找一個 cycle 恰好經過每個 vertex 一遍)
  2. Forumla Satisfiability: 給你一個布林運算式 (就是一串變數與 and/or, 每個變數的值只能夠有 true 或 false) 請找出一組變數的值, 讓最後的運算結果為 true。
  3. CLICQUE: 給你一個 graph, 請找出一個大小為 k 的 complete subgraph
  4. Vertex Cover: 給你一個 graph, 請找出一組 k 個 vertices, 它們罩住整個 graph (沒有一根 edge 逃得掉)
  5. Subset Sum: 給你一些自然數, 請找出其中某些, 其和為 k

...

  1. a famous reduction graph
  2. A long list of NP-complete problems
  3. NP
  4. some reductions