破解计算机科学 P 与 NP 问题的复杂性代码
图片来源：滑铁卢大学 滑铁卢大学的新研究正在解决理论计算机科学中最大的问题之一。但根据卡梅伦·赛斯博士的说法，做到这一点的方法。研究人员在算法近似领域工作，就是将问题分解成更小的部分。 “每个从事计算机科学和数学工作的人都知道‘P vs. NP’问题，”Seth 说。 “这是臭名昭著的千禧年奖问题之一：如此著名且如此困难，解决一个问题就能让你赚到一百万美元。” 要理解“P vs. NP”问题的关键，请想象一个巨大的拼图游戏或数独游戏。如果计算机可以相对较快地解决它，那么它就是“P”问题，而如果它们非常难以解决，但提供的解决方案可以很快得到验证，那么它们就是“NP”问题。 例如，数独谜题可能需要花费很长时间（可能是几个小时）才能解决，但一旦提供解决方案，只需几秒钟即可检查所有列和行是否具有正确的数字。 “在 P 与 NP 中，让每个人彻夜难眠的问题是，是否每个可以快速检查的解决方案也是一个可以快速解决的问题。是不是每个易于验证的问题也很容易解决？” 计算机科学中这一挥之不去的问题的实际意义影响着密码学、人工智能和优化领域的重大研究和发展。用于各种敏感网络的最常见的加密方法依赖于这样的假设：存在极难解决但易于验证的问题。这是从在线密码到安全银行转账的所有事物的基本逻辑。 赛斯的研究不是直接解决问题，而是寻找近似问题的解决方案。 “我正在做的是研究一系列与更广泛的 P 与 NP 问题相关的较小问题。本质上，我要问的是我们是否能够解决这些其他相关问题，”Seth 说。 例如，他最近对图算法的研究设想了一个具有大量连接的巨大网络，就像人们可能在大型在线社交网络应用程序中找到的那样。赛斯从图形网络中切出了一小块，并询问这一小块拼图可以告诉我们什么关于整体的知识。 这项技术创新提供了一种组合工具，可以帮助解决复杂的优化问题。这些工具将大量可能的组合减少为可管理的子集。从这个意义上说，赛斯的基础研究正在解决计算机科学中这些更艰巨的问题。 “我在研究中所做的并不是试图找到一个解决方案，而是要确定是否存在接近的解决方案，以及这可能会教会我们关于整套类似问题的什么。” 论文“A Tolerant Independent Set Tester”发表于 2025年计算理论研讨会。研究结果是 发表 于 arXiv 预印本服务器。 更多信息： Cameron Seth，一位宽容的独立测试员， arXiv （2025）。 DOI：10.48550/arxiv.2503.21441 期刊信息： arXiv 由滑铁卢大学提供 引文：破解计算机科学 P vs. NP 问题的复杂性代码（2025 年，11 月 14 日），2025 […]