Russell Impagliazzo在1995年的一篇经典的论文中描述了P和NP问题具有不同程度可能性的5个层级：
- 算法：P=NP或理论上等效，例如NP的快速概率算法(fast Probilistic algorithm)
- 启发式：NP问题在最坏的情况下很难求解，但平均来说还是可以得到求解的
- Pessiland：我们可以轻松的创建困难的NP问题，这是所有可能中最糟糕的，因为我们既不能在平均意义上解决难题，也不能从这些问题的难度中获取任何明显的优势
- Minicrypt：存在加密的单向函数的问题，但我们没有公钥加密
- Cryptomania：公钥密码学，也就是说，两方可以通过公开渠道来交换加密信息，然后通过公钥解密
上述的5个层级没有正式的定义，都是通过人们对P和NP问题的了解人为规定的。但是人们普遍认为，Cryptomania这个等级的可能性最高。
Impagliazzo借鉴了P和NP理论中的核心思想——“我们无法拥有一切”。
我们或许可以解决困难的NP问题，或者解决密码学的重要关键，但是不能将两者同时攻克。
不过，也许我们正在走向事实上的Optiland——机器学习和软硬件优化等方面的长足进步让我们能够在一定程度上解决当年无法设想的问题，包括语音识别、蛋白质折叠解析等。但是大多数情况下，我们的密码协议仍然是安全的，所以不用太担心。
在2009年的综述中，我曾经在其中“如果P=NP怎么办”的章节中提出，通过使用奥卡姆剃刀法则，学习将会变得容易——我们只需要找到与数据一致的最小程序，也就是问题的关键核心。那么此时，原本十分难以解决的视觉识别、语音识别、翻译以及其他的任务都会变得微不足道。我们还将对天气、地震和其他自然现象做出更好的预测和理解，以及建模。
今天，我们可以使用人脸识别解锁手机，可以和一些智能设备语音对话来提出问题并且得到理想的回答，可以将我们说的话、输入的文字翻译成另外的语言。我们的手机会收到关于天气和其他突发事件的警报，它的预测效果比我们之前十几年前能做到的效果好的多。与此同时，除了对小密钥长度进行类似暴力破解的攻击之外，我们的密码学基本上还是很鲁棒和安全的。那么现在，让我们看看计算、优化和学习方面的最近进展如何将我们带到Optiland中吧！
No post found!
为了方便大家，我们特此分享一些来自公共平台的文章供大家阅读。这些文章仅供参考，不代表本站编辑的观点、立场和态度。这些文章中的一切内容版权皆属于原作者或原平台。若涉侵权请予以告知，我们将尽快删除相关内容。谢谢！
Latest posts by 文章转载 (see all)
- 《纽约客》丨纪念9·11二十五周年 - 09/12/26
- 数学500年：新的黄金时代？（1） - 06/05/26
- 没有美洲，我们吃啥？ - 05/17/26