各位真强者、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币，所以就不赘述了。