本文轉貼自PTT
台灣最大的本土社群網站
分享這篇文章到Facebook、Google+或噗浪！


 作者  LPH66 (杇瑣)                                                看板  Math 
 標題  Re: [其他] 踩地雷數學疑問?                                             
 時間  Fri Sep 28 04:39:51 2012                                               
───────────────────────────────────────


來寫點跟這些玩意有關的東西好了

(這些是屬於計算機理論的東西  是近幾十年才出現的理論

 咱們資工系在研究的東西就是從這裡堆上來的 (遠目))

-------------------------------------------------------------------------

什麼是 P vs NP 問題？

這裡是數學版就講一點數學上的定義好了

P 跟 NP 都是所謂的「複雜度類」(Complexity class)

它們都是集合  集合的成員是許多的「問題」

這些問題都是所謂的「是非題」

例如  「給定一張地圖  問有沒有一條路徑恰好走過每條路一次」

像這樣子的問題

(如果像是「給定一張地圖  問恰好走過每個點一次的最短路徑有多長？」

 這種問「量」的問題則可以藉由增加一個量的參數把它轉化成像是

 「給定一張地圖和 K 值  問有沒有一條恰好走過每個點一次的路徑比 K 短？」

 這樣的是非題  然後重覆詢問這個是非題去得到所求的量的答案

 因此也可以使用這種分類法)

這種問題都會有一或數個可變動的參數  表示題目的大小

例如上面那個問題參數可能包含「交會點的數目」或「路的數目」等等

一般來說  這個參數越大要解開題目所花的時間就會越多

有的題目  即使參數變成十倍  時間只要多一下下就好

有的題目  它的參數變成兩倍  時間就要兩倍

有的題目  即使參數只多個一  時間就要兩倍

那分類這些題目的方式就是使用這種「複雜度類別」

上面說的是對時間分類  所以稱做「時間複雜度」

這是最常見的一種分類法

當然要談計算時間就要說明是在什麼樣子的計算模型下計算

也就是說要說明「到底做什麼事會花多少時間」

基本上常用的是所謂「確定型圖靈機」(Deterministic Turing Machine)

這東西只要大概想像成和咱們現在的電腦差不多就行了

因為這東西如果要細說它的數學定義那就又要一篇了 XD

(不知道各位記不記得今年 6/23 這個 Google doodle:

 http://www.google.com/doodles/alan-turings-100th-birthday

 這玩意就是一個確定型圖靈機

 這是 Google 紀念這套計算機理論的建基者 Alan Turing 的一百歲生日做的)

回到原來的問題

剛剛說 P 跟 NP 是複雜度類

它們是屬於剛才提到的對時間分類的複雜度

P 是表示「解決問題所需要的時間至多是參數的多項式函數」

也就是說  頂多是參數兩倍的話時間變八倍或十六倍這種程度而已

(計算機理論裡通常簡稱這樣的時間花費叫做「多項式時間」

 因為這個敘述太常用了但每次都這樣講會很拗口...)

而 NP 則是表示「給定問題和一個聲稱的答案

要檢查這個聲稱的答案是不是真是答案  需要多項式時間」

雖然聽起來好像差不了多少  但很多時候我們知道一些題目求解跟證明它是解差很多

例如質因數分解  給一個幾百位的數求分解會死人

但是如果是給一個幾百位的數和一個聲稱是它的質因數分解的答案

那我們只要先檢查這聲稱的答案裡的數字是不是真是質數

然後再把它乘起來看看就可以確定了

像這樣的問題就會在 NP 裡

P vs NP 問題就是問說這樣子的兩個集合到底是不是同一個

之所以會這麼問是因為

NP 裡面有些問題如果要去解它所需要的時間通常會是參數的指數函數以上

這代表參數只要加一  時間就要變成幾倍

但現在卻不知道這些問題有或沒有需要多項式時間的解法

(不知道是真的不知道喔  也就是目前沒有證明也沒有反證)

(順帶一提  並不是所有需要時間至多是指數函數的問題都在 NP 喔

 有另一個時間複雜度類叫 EXPTIME 的才是指這種問題

 而其實上幾行的指數函數也不怎麼對

 因為現在有些問題目前已知需要的時間

 沒有到指數函數那麼扯但又沒有多項式函數那麼和藹可親)

這些問題的一部份特別被叫做 NP-Complete (NP完全)

它收集的問題具有下面這個性質

「它屬於 NP，而且其他任何一個屬於 NP 問題都可以花費多項式時間轉換成這個問題」

它對 P vs NP 問題的貢獻就在於

只要一個 NP-Complete 問題被證明能夠以多項式時間解決

那麼根據這個性質  所有的 NP 問題就都能以多項式時間解決  於是就證明了 P = NP

反過來  只要一個 NP-Complete 問題被證明不能夠以多項式時間解決

那麼因為這個問題屬於 NP 但卻不屬於 P  所以 P≠NP

無論哪一個都是解決了 P vs NP 問題  (附帶一筆一百萬鎂的獎金)

不過  「NP-Complete」這個概念自從 1971 年被提出來之後

現在已知有至少三千個問題是屬於 NP-Complete 的

但是四十年來沒有人能對其中即使任何一個給出多項式時間的解法或證明不存在

甚至連兩年前號稱證明了 P≠NP 的那位 Vinay Deolalikar 他的證明

也被其他專家找出了幾個重大錯誤

這個問題才被稱為是世紀難題之一

另外要講的一個常見誤解是: NP (或 NP-Complete) 表示「無解」  這是錯的

(而且大概十有八九是被 NP 的 N 字給誤導了)

它只是不知道有沒有「很快的解法」而已

因為總是有一個「解法」叫做「暴力測試」  就是把所有可能答案都扔進去試一試

只是所有的可能答案個數是參數的指數函數  要暴力來的話很慢而已

-------------------------------------------------------------------------

那，它跟踩地雷有什麼關係？

總算回到原 PO 一開始的問題了

這位 Richard Kaye 教授他在 2000 年時

在 Mathematical Intelligencer 這個雜誌上投稿了一篇文章

這篇文章證明了下面這個「踩地雷問題」是 NP-Complete:

「給定一個盤面，包含一些已經打開的數字和可能會有的一些已經標記的地雷，

  是否存在一個地雷分佈使得這個盤面能夠出現？」

在 NP-Complete 問題已經被研究了這麼久的現在

要證明一個問題屬於 NP-Complete 通常是用這個方法:

去找另一個 NP-Complete 問題  然後試著用多項式時間把那個問題變成這個問題

根據上面提到的 NP-Complete 問題的性質  這樣就證明了這個問題是 NP-Complete

(轉不過來的話再仔細想一想 XD)

這篇文章所選用的另一個問題是所謂的「可滿足性問題」:

「給定一個邏輯式子 (也就是由 And/Or/Not/什麼有的沒的連接的式子)，

  是否能夠將式子中的變數取定 True 或 False 使得整條式子得到 True？」

這個問題是當年 NP-Complete 這個概念被提出來時

所證明的第一個屬於 NP-Complete 的問題

(當然因為是第一個所以不能使用上面這個方法

 所以是直接證明「可滿足性問題」具有 NP-Complete 的性質

 這個如果要寫又要一篇了 XD)

而 Kaye 教授所使用的把這個問題變成踩地雷問題的方法是.....

                     直接在踩地雷的盤面上畫邏輯電路圖！

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf

這個是 Kaye 教授放在他的個人網站上的 pdf 檔

(http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ 原始來源)

裡面展示了一些他在那篇文章裡所用到的「電路圖元件」

例如「電線」、「Not 閘」、「Xor 閘」、「And 閘」等等

利用這些「元件」就能夠在踩地雷盤面上拼出一個邏輯電路圖出來

也就是說  「一個邏輯電路能不能成立」轉變成了「一個踩地雷盤面有沒有解」

這樣就證明了這個「踩地雷問題」是 NP-Complete 了

原 PO 你的問題看了這裡列的這些「元件」大概多少能夠有一點感覺吧？

-------------------------------------------------------------------------

可是這個證明用的是自己設定的地雷吧？這樣的話那那些隨機的怎麼辦？

這個問題有點誤解了這個證明

這個證明是在說

「現在我用踩地雷盤面畫了這個電路圖

  如果有哪個傢伙有辦法對所有踩地雷盤面都可以快速解

  那我這個盤面也要能解

  而這個盤面的解可以變成可滿足性問題的答案」

也就是說  他其實不是在證明他找到了快速方法

反而是證明了幾乎不太可能找得到快速方法來解

(不然我們就證明了 P = NP 了)

-------------------------------------------------------------------------

總覺得這個「踩地雷問題」跟平常的踩地雷還是沒什麼關係...

當然有關係啊 XD

當我們想測試某個格子是不是地雷時

就把現在的盤面複製一份  把那個格子標上旗子

然後丟給這個問題的解決方法  如果它說這是不可能的那這一格就絕對安全

同樣的  如果那一格標上 0 ~ 8 再丟給這個問題去解都說不可能的話

那這一格就可以標旗子了

這正是一個解平常的踩地雷的演算法 XD (雖然慢透了就是)

(不過通常的踩地雷是還有另一個線索叫做「剩餘地雷數」

 有的時候這是可以做為推理的材料的

 這個演算法並不使用這個線索  也就是說它並沒有特別限制剩餘地雷數)

-------------------------------------------------------------------------

好吧，那這個教授為什麼會想到要去證明這個？

根據他自己的說法

是因為有的時候我們必須得要看過整個盤面才能確定下一步要怎麼做

┌────────┐  像是左邊這個他舉的例子  ＊是已經標出來的地雷
│２３＊２２＊２１│
│＊＊５　　４＊２│  要確定？那一格安不安全
│　？＊＊＊　４＊│
│＊６　６＊＊　２│  非得把幾乎所有還沒開的格子都檢查過一遍
│２＊＊　５５　２│
│１３４　＊＊４＊│  還要做幾個假設才可以導出那一格是安全的
│０１＊４　　＊３│
│０１２＊２３＊２│  這跟 NP-Complete 問題的那種「暴力解法」有種相似的感覺
└────────┘
                      所以才會去試著證明它屬於 NP-Complete

-------------------------------------------------------------------------

嗯，踩地雷的部份瞭解了，那密碼學又是怎麼一回事？

這個其實是只要提到 NP-Complete 或 P vs NP 問題時 99% 會舉的例子

那就是 RSA 公開金鑰加密演算法

因為這是實際上有著廣泛應用的東西  而又能夠跟 P vs NP 問題扯上關係

比較能夠有「這似乎是這個理論的實際應用」的感覺 (雖然實際上大概不會是 :P)

細節不多說  重點在於 RSA 的加密安全性是建立在

「將一個幾百位的大數字做質因數分解目前沒有快速的方法」這個事實上

(尤其要注意的是  「質因數分解」這個問題只已知屬於 NP

 是不是屬於 NP-Complete 都還不知道)

但是如果 P = NP 被證明的話

那麼屬於 NP 的質因數分解就會存在一個多項式時間的做法

這樣一來 RSA 的安全性就會崩潰

-------------------------------------------------------------------------

一個題外話

其實 RSA 不需要到 P = NP 才會崩潰

因為早在 1994 年就有一個叫做 Peter Shor 的傢伙

給出了一個在「量子電腦」上用多項式時間做質因數分解的演算法

這就是上面提到的「計算模型」的不同

平常沒有明說的時候都是使用「確定型圖靈機」這個計算模型

因為它最接近我們目前使用的電腦的計算模型

NP 其實有另一個使用「非確定型圖靈機」的計算模型的定義

(NP 的 N 字其實就是指這個「非確定型圖靈機」  而不是什麼「非P」的)

這裡則是「量子電腦」這個計算模型

所以當年 IBM 的那些人號稱實作了這個演算法時可想而知有多轟動 XD

-------------------------------------------------------------------------

目前能講的就這些了

這些計算機理論的東西要講深下去就等於是咱們資工系的一門課了

那可不是這裡幾篇文章就可以講得完的東西 (遠目)

-------------------------------------------------------------------------

Reference:

* Richard Kaye 教授的網站; 這是關於踩地雷的部份
  http://web.mat.bham.ac.uk/R.W.Kaye/minesw/

* 由某未知來源找到的該篇雜誌文章 :P

* 維基百科的許多條目

* 本人的修課記憶 XD

--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
                      ---'Harry Potter and the order of the phoenix', P513

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.218.108.125
推 THEJOY      :有看有長知識推 :P                                  09/28 05:11
推 jurian0101  :想像中的LPH是「夏日大作戰」那種會在日常生活把Shor  09/28 06:49
→ jurian0101  :演算法拿來當消閒讀物的人:3                         09/28 06:50
→ sardine     :板上應該不少神人的休閒讀物都相當有趣               09/28 07:32
推 WINDHEAD    :推專業XD                                           09/28 08:05
→ goshfju     :超專業 XDD                                         09/28 09:24
推 coda17      :相當專業XD                                         09/28 11:06
推 TassTW      :這不推對不起良心啊                                 09/28 11:10
推 johncai     :真的超專業，不過我沒看完@@                         09/28 16:50
推 sunev       :如果能提一下NP Hard就更完美了∼                    09/28 20:52
推 suhorng     :推                                                 09/28 22:06
推 bohsing     :WOW!!                                              09/29 01:07
推 iamwjy      :推推推                                             09/29 09:32
推 hcsoso      :終於有人出來寫複雜度理論的介紹了, 大推!            09/29 12:51
推 coolbetter33:推                                                 09/29 14:44
推 godgunman   :推!!   (真是太巧了在這裡看到LPH XD                 10/09 00:21
推 weeeeeeeeell:朝聖推!! 論文挺有趣的, 這篇也深入淺出              12/12 05:47
推 bbenson     :朝聖推!!                                           06/01 10:30
推 Frobenius   :朝聖推!!                                           06/01 22:18
推 kanonehilber:推                                                 06/03 13:35

----本文使用PCMAN+BBI轉貼----


※ 新版PCMAN開放測試中，新增功能：    



用PCMAN+BBI連回PTT原文