推 moso23 :直接解踩地雷運算會比較有說服力嗎?...*-.-* 06/02 17:09
推 JohnMash :直接以破解提款卡密碼為例 如何? 06/02 17:24
你還可以問, 判斷圍棋的征子成不成立是什麼問題? 會比踩地雷難嗎?
判斷征子不是很簡單嗎? 但征子成不成立是 PSpace-complete, 比 NP 更高一級
如果這樣就能說服別人征子是個難題, 那麼就不會有人願意出100萬美金解決NP=P問題了
※ 編輯: id010406 來自: 221.169.231.152 (06/02 17:37)
推 moso23 :什麼是圍琪貞子?....Q口Q 06/02 17:50
征子就是一連串的叫吃, 最後把對方逼到無路的一種圍棋走法. 這要有圖才比較好說明,
總之是初學者就學會的走法. 如果你有會下圍棋的朋友, 你告訴他判斷征子成不成立是
一個很難很難比踩地雷破密碼都難的問題, 他一定會覺得你在唬爛, 因為我告訴別人這
件事時, 沒有一個人相信. 他們會覺得你根本就是不懂, 然而事實就是這樣.
※ 編輯: id010406 來自: 221.169.231.152 (06/02 18:00)
推 moso23 :好難懂....我還學野球拳好了~..../__\ 06/02 18:02
推 xcycl :推 06/02 19:06
推 suhorng :推 06/02 19:27
推 gj942l41l4 :推 06/02 21:00
推 Chatterly :推好文 06/03 01:49
推 WINDHEAD : 06/03 03:05
推 TWN2 :征子有點類似貞子 只是她會從圍棋棋盤裡爬出來 06/03 06:10
推 jklkj :可以再講講PSpace-complete的問題嗎!!!!! 06/03 13:22
複雜度有分兩種, 一種是時間複雜度, 一種是空間複雜度
P 和 NP 指的是時間複雜度, 直觀地用電腦比喻, 就是一個程式執行起來,
需要多少時間(或者說要執行幾個指令)
凡是屬於P的問題, 都可以設計出一個在多項式時間內就能解決問題的程式.
而PSPACE 和 Log Space 指的是空間複雜度, 直觀地用電腦比喻,
就是一個程式執行過程, 會佔用多少記憶體
PSPACE 指的是這個問題, 可以設計出一個佔用多項式記憶體就把它解決的程式.
比方我們要解 n 個 m*m 矩陣的乘法, 加法等一連串運算.
n 個 m*m 的矩陣相乘, 寫個最簡單的程式 O(n*m^3) 就能解決, 所以這個問題屬於 P.
而我們這個程式在執行的時候, 用了一個 m*m的矩陣暫存運算的中間結果,
也就是空間複雜度是 O(m^2), 所以這個問題也屬於 PSPACE
1. derterministic 或 nonderterministic 只影響時間複雜度, 但對空間複雜度來說
不重要. 目前不知道 P 是否等於 NP, 但 PSPACE=NPSPACE
2. PSPACE 包含或等於 NP, 也就是說凡是屬於 NP的問題都可以用多項式空間就解決,
但反之不一定.
征子是 PSPACE-complete的證明可以搜尋關鍵字 "ladders are pspace complete"
以下是其中一個 source http://dl.acm.org/citation.cfm?id=647481.728110
證明的方法就和前面 LPH66 大所講的踩地雷證法的原理是一樣的, 其他就請強者補充了
我發覺講了半天我竟然沒寫 deterministic 和 nonderterministic turing machine
的定義 :Q 不過還是交給強者, 我只補充說一下為什麼這些運算問題是邏輯問題.
現在我們用的電腦, 它做整數除法, 其實是做了一連串的邏輯運算. 考慮一艘在外太空
故障的太空船, 沒有紙筆和電腦可以使用, 但是太空人必須在一秒內算出兩個大整數
p, q相除的結果, 準確到小數點下10位, 即時修正航線, 否則就會失事.
於是他們就把一些砝碼湊成 q, 然後裝上一個引擎, 施力 p, 而他們還有一個很準確的
測速器, 在一秒後, 測出砝碼的速度 v到小數點下10位, 根據牛頓第二定律 v=p/q
於是這整個砝碼, 引擎, 測速器等, 就構成了一個做除法的計算機.
計算機並不是只侷限在我們現在所用的電腦, 事實上世間萬物每秒都在運算. 但是上面
那個太空船的計算機, 和電腦不同的是, 它做除法並不是做邏輯運算. 這種計算機如果
測速器更精準一些, 那就可以在更少的時間內, 算出更大的整數相除, 到小數點下更多
位數, 甚至比我們用電腦還快. 可是因為量子力學的限制, 它會有一個極限. 這種計
算機能算多快, 是一個物理問題.
如果 Hamitonian cycle 這個NP-complete的問題, 也有像整數除法一樣, 有個對應的
物理計算機, 那麼它能多快時間解出來, 就是個物理問題, 和P等不等於NP無關.
而 turing machine 做的是邏輯運算, 某個問題能不能在多項式個步驟就完成, 並不是
由量子力學來決定. 它是邏輯運算能多快的問題. 大致很粗略的想法就大概是這樣.
※ 編輯: id010406 來自: 221.169.231.152 (06/03 15:05)
推 yeh6 :推阿! 雖然有些還是看不太懂 可以講講 那些定義嗎XD 06/04 01:01
用比較直觀的說法, 一部計算機, 如果它有個 cpu, 而這 cpu的所有可能狀態是有限的,
就叫做 "有限狀態機", 比方我們現在使用的電腦就是.
如果有限狀態機還有一塊無限大的記憶體, cpu有個讀寫頭可以讀寫記憶體, 那麼它解
決問題的能力就和turing machine等價.
而如果cpu根據它目前的狀態, 就決定了它下一步要做哪一個指令, 那就叫
deterministic 機器. 我們現在使用的電腦就是 deterministic machine.
如果cpu下一步會做哪一個指令, 是一個可能的集合, 並不唯一, 那就叫
nondeterministic 機器. 重點在於, 它會執行集合中哪個指令, 並不是隨機的, 而是它有
"無限洞察力". 也就是說, 如果這個問題有解, 那麼這個 cpu 就會在所有可能的指令
中, 執行會解決問題的那個指令, 好像它已經知道答案是什麼那樣.
比方我們要解這個版上出現過的問題: 在 1到 100間, 是否能找出不同的8 個整數,
使得它們的倒數和等於 1?
一個 可能的 deterministic 程式, 有 8層迴圈
for(x1=2 to 93) for(x2=x1+1 to 94) for(x3=x2+1 to 95).....
for(x8=x7+1 to 100)
{
if (1/x1+1/x2+1/x3+...+1/x8==1) then return x1 x2 x3....x8
}
最壞可能要做 O(100^8) 那麼多組
但是 nondeterministic 程式, 只要做 8 步
1. 在 1到93之間選一個數為 x1
2. 在 x1+1 到94間 選一個數 為 x2
....
8. 在 x7+1 到 100 間選一個數 為 x8
return x1 x2 x3....x8
這個程式每一步會選哪個數字並不是隨機亂選, 因為它有 "無限洞察力", 如果 x1=3
有一組解, 那麼cpu執行第一行就會把 x1 設為 3. 接下來如果 x2=7 有一組解, 那麼
第二行就會把 x2 設為 7, 如此繼續下去.
這種機器當然只是理論上的. 這種理論有什麼意義? 有人可能會懷疑這和算命仙的水晶
球有什麼不一樣.
差別在於, 我們問算命師ABC猜想成立嗎? 他只告訴我們是或否, 至於相不相信, 在個人.
但是 nondeterministic machine 是一位 "超級數學家", 你問他ABC猜想成立嗎?
他說是, 然後你說證明給我看, 他就開始打出一串證明, 告訴你第一步你要選什麼,
第二步你又要做什麼,依次做給你看.
也就是說, 我們不知道這位數學大師怎麼推理的, 可是他會有個證明讓你檢驗, 而如
果這個檢驗只需花多項式個步驟, 那麼這個問題就屬於 NP
比方說, 或許我們窮一生之力的時間也無法證明ABC猜想, 因為有太多可能性, 但一旦
有一位大師寫出證明, 我們或許只要一個星期就能驗證這證明是對的.
而 Cook 的貢獻, 就是證明了一個特殊的問題: propositional logic的 satisfiability
問題, 簡稱 SAT. 只要存在一個多項式個步驟就能解決SAT的演算法, 那麼對那些屬於NP
的問題, 也就是在多項式個步驟內就能驗證的問題, 我們不需要這位 "超級數學家", 自
己就能在多項式個步驟裡找到證明.
所以只要SAT有很快的演算法可以解決, 也就是說如果 NP=P, 那就幾乎如同我們在NP
問題方面具有 "無限洞察力"一樣, 這當然是相當不可思議的事情. 所以了解NP會不會
等於P在理論上很重要.
但問題是, 像ABC猜想那類的問題, 是屬於所謂的 PSPACE 而不是 NP. 因為用來
表達大多數學公理系統的, 是所謂的 first order logic, 一階符號邏輯. 這類問題
是 PSPACE-complete, 它有時候即使是驗證證明的對錯也需要指數式個步驟. 更糟
的情形就是 Kurt Godel證明的, 有些定理沒有辦法從這個公理系統得到證明或反證.
遇到這種情況, nondeterministic machine 這位超級數學家會無限地執行下去, 而我們
不知道他會不會停.
所以即使我們對NP問題有了無限洞察力, 應該也還是有很多工作要做.
※ 編輯: id010406 來自: 221.169.231.152 (06/04 23:53)
推 Arton0306 :只能推了！ 06/05 23:00
推 lemmii :推好文 07/28 05:23