各位真強者、pavone、E cup、30cm、勝利組、高富帥、金城武、溫拿、小妹，
大家好！打給後！胎嘎後！AV8D！口泥幾哇！安安！
以下是本魯的朋友告訴本魯的。
※ 引述《Zawar379 (露草)》之銘言：
: P/NP問題
: 是很多數學家究其一生想解決的數學難題
: 據說只要把這問題解開，天底下所有的密碼系統就統統崩潰了
應該是說如果答案是NP=P，那密碼系統就崩潰了～
: 有這麼厲害嗎？
: 既然如此，專幫解winrar密碼的yoyo大不就會因此失業了？
: 本著好奇心，小魯也去wiki看了一下，但是前幾句話就看不懂了，實在非常懊惱
: 有沒有P/NP問題能讓全世界密碼崩潰的八卦？
NP問題的一種等價定義是「可以有效率地驗證答案的問題」，雖然原始定義應該是用
nondeterministic的計算來定義的～
有一個著名的NP-complete問題叫做subset sum problem，這個問題的輸出和輸入如下：
輸入：一堆整數和一個目標值。
輸出：如果輸入的那堆整數中，有一部分加起來等於目標值，就回答「是」，否則回答
「否」。
什麼叫做「可以有效率地驗證答案」呢？以subset sum problem來說，就是如果輸入當
中真的有一部分加起來等於目標值，那你可以直接告訴我是哪一部份，我可以很簡單地
驗證你的證明：加加看，就知道你有沒有騙我了～
恰好subset sum problem也是NP問題當中眾多最難且互相間一樣難的問題之一，這種問
題叫做NP-complete問題，較多人不知道的是，除非NP=P，否則NP當中會有一些問題既
不NP-complete，也不屬於P（這個意思就不贅述了，不是本文重點，其實本文的重點只
是賺P幣）。
八卦是「可以有效率地驗證答案」這件事的玄機，在上面的例子中，我們說你要告訴我
哪部分加起來等於目標值，我才有辦法驗證你有沒有騙我，可是「PCP定理」告訴我們：
你可以寫下某一個「證明」（其實也就是一段文字的意思），我可以驗證你的
證明對不對～如果輸入的整數中，真的有一部分相加等於目標值，那麼我會很
快被你的證明說服，否則若沒有任何一部分相加等於目標值，那麼無論你拿出
的證明多麼精心設計，通過我驗證的機率都很低～然後～～登登登，關鍵來了
，我需要看你的證明當中的幾個字呢？只有常數個就夠了！也就是我需要看你
提供的證明當中的字數，與原本輸入的那堆數字到底有多長根本無關！
大意就是：對subset sum problem與其他所有的NP問題來說，一件事情的「可以驗證的
證明」只要設計得宜，就可以讓驗證者只需要看其中極短部分，該部分的大小和要被證
明的事情的長度根本無關。
以上說的事情其實和某些NP問題的「不可近似性（inapproximability）」是等價的，
不過因為本魯的朋友只想賺賺P幣，所以就不贅述了。