像许多计算复杂性领域的研究者一样，兰斯·福特诺（Lance Fortnow）——伊利诺伊理工学院计算机学院的前院长兼教授——花费了大量时间思考他所谓的P-NP问题的核心所在。（他在2007年发表于《Communications》杂志的一篇文章中开玩笑说：“这个问题仍然没有解决。”）他还致力于让更广泛的读者群体了解这个难题，尤其是通过他的2013年出版的科普书籍《The Golden Ticket: P、NP与不可能性的探索》。在书中，他与莉亚·霍夫曼（Leah Hoffmann）讨论了这个项目、他自己的研究，以及P-NP问题对未来计算技术的影响。
你在复杂性理论方面的早期工作，尤其是在交互式证明方面的研究，发生在20世纪80年代末到90年代初的一个充满创新活力的时期。你能向我们详细介绍一下那个阶段吗？
我不知道你是否读过拉斯洛·巴拜（László Babai）的论文《电子邮件与交互的意想不到的力量》。他在论文中讲述了许多有趣的故事。那时互联网还没有真正普及，我们主要是通过电子邮件来交流研究结果。1989年，诺姆·尼桑（Noam Nisan）发表了一篇论文，指出利用多个证明者可以证明某个命题是错误的。这让我非常惊讶，因为我认为这样的命题应该很难证明，但他却做到了。于是我研究了这篇论文，并与卡斯滕·伦德（Carsten Lund）和霍华德·卡洛夫（Howard Karloff）一起，利用一种称为“求和检查协议”（sum-check protocol）的方法，成功实现了仅用一个证明者就能完成证明的目标。
求和检查协议如今被应用于zk-SNARK（零知识简洁非交互式论证）技术中，这是区块链加密的基础。
有趣的是，计算复杂性理论的应用范围非常广泛。
你的论文发表后不到两周，阿迪·沙米尔（Adi Shamir）将这一成果推广到了PSPACE类问题，证明了IP类问题（可以通过交互式证明解决的问题）实际上包含了PSPACE类问题（即可以使用多项式时间复杂度解决的问题）。
这让我开始思考多个证明者的应用场景。随后，卡斯滕、拉斯洛·巴拜和我共同发表了一篇论文，证明利用多个证明者可以解决所有非确定性指数时间复杂度的问题，这一成果后来被扩展到了PCP定理的范畴（不过这项工作并非由我完成）。之后我又在交互式证明方面做了一些研究，但当时我认为这个领域已经发展到了顶峰。然而我大错特错！之后我转向了其他研究方向。
2013年，你出版了一本科普书籍《The Golden Ticket》，专门探讨了计算复杂性领域最重要的未解问题之一——P-NP问题。
大约在2007年，《CACM》杂志的主编摩西·瓦尔迪（Moshe Vardi）邀请我撰写一篇关于P-NP问题的综述文章。我面向的是普通读者群体，这本书非常受欢迎，目前下载量已超过30万次。
那时我想，这本书可以进一步拓展成一本完整的科普书籍。目前关于计算机科学的科普书籍很少，虽然有很多关于技术和社会的书籍，但很少涉及计算领域内部的原理。于是我联系了普林斯顿大学出版社（Princeton University Press）并开始写作。
这本书很好地向非技术读者解释了P-NP问题。你能简单总结一下这本书的内容吗？
当然可以。假设你在Facebook工作，马克·扎克伯格（Mark Zuckerberg）找到你说：“我们有一个庞大的数据库，知道哪些人互相是朋友。我想让你利用这个数据库和高速计算机来找出Facebook上是否存在200个互相是朋友的人。”
要解决这个问题，可以逐一检查每200人的组合是否都是朋友关系。对于每个组合来说，需要检查大约1万条友谊关系，这还算可行。但Facebook上有大约30亿人，因此组合的数量实在太多。
或许有更聪明的方法，比如先找到小规模的派系群体，然后再将它们合并。但目前还没有比逐一尝试所有可能性更高效的算法。而是否存在这样的算法正是P-NP问题的核心所在。如果有人给出了解决方案，验证起来相对容易；但要实际找到这个解决方案可能非常困难。
事实上，有很多类似的问题属于NP完全问题（NP-complete problems），比如为旅行推销员规划穿越多个城市的最短路线。
这类问题还有成千上万种。有趣的是，它们之间是等价的：如果能解决其中一个问题，就等于解决了所有这类问题。如果P不等于NP，那就意味着这些问题都没有解决方案。这个问题已经存在了50多年，但我们至今仍未找到答案。
P-NP问题可能仍然没有解决。不过正如你在最近发表于《CACM》的文章中所提到的，它对未来计算技术的发展可能并没有太大影响。
在我的书中有一章名为“美丽的世界”（The Beautiful World），其中描绘了一个P等于NP的理想未来。回顾过去，很多预测如今正在通过人工智能和优化技术的进步变为现实。例如，比尔·库克（Bill Cook）成功设计了游览英国所有酒吧的最短路线。
然而，这些技术在密码学领域至今尚未取得突破。这听起来似乎好得令人难以置信。
1995年，拉塞尔·因帕利亚佐（Russell Impagliazzo）提出了“五个世界”的概念：如果P等于NP，那么世界会处于哪种状态？一种可能是“算法世界”（Algorithmica），在这个世界里P等于NP，所有问题都能轻易解决；另一种可能是“启发式世界”（Heuristica），在这个世界里我们通常能够解决NP问题；还有一种可能是“密码学灾难世界”（Cryptomania），在这个世界里公钥加密技术无法使用；而中间的一种则是“佩西兰德世界”（Pessiland），在这个世界里NP问题难以解决，同时不存在单向函数，因此我们既无法解决复杂问题，也无法从问题的难度中获得任何密码学优势。
有趣的是，我们似乎正朝着一个看似理想但难以实现的目标前进。我称之为“奥普蒂兰德世界”（Optiland），在这个世界里我们可以解决所有关心的问题，同时密码学也能保持安全。
你认为这种情况真的会发生吗？
看起来我们确实正朝着这个方向发展。有人提出了一些可能的原因，我认为这与数据压缩技术有关。如果有人发明新的算法或制造出量子计算机，密码学可能会受到威胁。但我认为，我们关心的问题会变得越来越容易解决，而密码学也会继续保持安全性。
莉亚·霍夫曼（Leah Hoffmann）是一位居住在纽约皮尔蒙特（Piermont）的技术作家。
