科学探索|我们生活在计算宇宙的哪个密码世界当中？( 二 ) 我们生活在计算宇宙的哪个密

大多数计算机科学家认为P不同于NP ，原因很简单， NP中有很多问题是我们无法有效解决的。然而，没有人能够证明（或反驳）这一点，尽管“P/NP”问题被认为是50年来理论计算机科学中最著名的问题，除了最聪明的人不断失败之外，我们没有证据表明 P不等于NP很难证明。
Heuristica
在这个世界中，有一些NP类问题很不容易解决，但每个NP类问题“平均”起来都很容易，意即在大多数情况下都可以有效解决。例如，如果我们生活在Heuristica世界中，那就存在一种几乎总会成功的高效行李箱打包算法，但对于行李箱和物品的一些罕见组合来说，它可能会失败（这些快速且通常成功的算法通常被称为“heuristic”）。
从密码学的角度来看， Heuristica和Algorithmica并没有太大的区别。如果我们在Heuristica世界中提出一种加密方案，就会存在一些快速的解密方法，可以对几乎每条消息进行处理，从而使得该方案在实际场景中毫无用处。
Pessiland
这是所有可能的世界中最糟糕的。在Pessiland世界中，一些NP类问题即使平均起来也都十分困难。对于这些问题，任何有效的算法都会失败——不是偶尔失败，而是经常失败。然而，这些难题对隐藏秘密信息而言却不是那么有效。
我们绝对不想住在Pessiland世界中，在这里，我们得到了（计算）复杂性的所有不好的方面，同时又没有任何像密码学那样的优势。
Minicrypt
在这个世界中， NP中的一些问题平均起来都很难，而这种困难程度足以构建密码学最基本的构建块：单向函数。这是一种可以有效执行但不能有效逆转的函数：对于每一个输入，函数值都容易计算；但对于一个随机的函数值，算出其对应的输入却很困难。密码学家已经证明，安全加密需要单向函数。如果单向函数存在，我们就会得到一系列实用的加密工具，比如秘钥加密、数字签名和伪随机数生成器。
毫无疑问，单向函数是否存在，是密码学中最重要的问题，如果没有单向函数，所有这一切都可能被破坏。事实上，如果单向函数存在，将证明P/NP问题中， P不等于NP；与之对应， P不等于NP的假设并不能直接推出单向函数的存在。
Cryptomania
在这个世界中，我们有足够的难度创建出Minicrypt世界中的任何东西，甚至还可以创建出更高级的加密协议，如公钥加密（在这种协议中，人们可以在不知道密钥的情况下发送加密的消息）。
对这些世界的筛选
大多数密码学家认为，至少有一些真正安全的加密方法是存在的，因此我们可能生活在Cryptomania或Minicrypt世界当中。但密码学家们并不指望很快就能看到这方面的证据。如果存在这样的证据，首先需要排除其他三个世界，而单单排除Algorithmica本身就已经需要解决“P/NP”问题。数十年来，计算机复杂度领域的科学家一直在努力解决这一问题，但至今仍未被解决。
不过，密码学家最近发现了一种筛选这些世界的新方法。他们第一次确定了一个自然问题——有时间限制的柯氏复杂性（time-bounded Kolmogorov complexity ，简称Kt）——的难度等级在包含密码学的世界和不包含密码学的世界之间划出了一条清晰的分界线，如果Kt问题普遍很简单，那么安全密码学就不可能存在，所以我们处于Algorithmica、Heuristica或Pessiland世界当中。但如果Kt普遍都很困难，那我们就能找到单向函数，从而证明我们至少生活在Minicrypt世界中，甚至可能处于Cryptomania世界。