L is different from NP
该论文声称提供了一个证明，证明复杂度类 LOGSPACE (L) 与 NP 类是不同的。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在计算机科学的广袤领域中，存在着一个关于效率极限的基本问题：一台机器解决某个问题究竟需要多少内存？想象一位图书管理员必须在一座图书馆中寻找一本特定的书。如果管理员只有一个小笔记本来记录一些页码，他们可以快速完成任务。如果他们有一个巨大的仓库来存储图书馆的所有细节，那么这项任务就变得微不足道了。复杂度理论根据计算机解决问题时所需的“笔记本空间”或内存大小，对问题进行了分类。其中一类被称为对数空间（logarithmic space），代表那些仅随输入规模的位数增长而增长、仅需极少量内存即可解决的问题。另一类被称为非确定性多项式时间（nondeterministic polynomial time），代表那些计算机可能需要通过“猜测”路径来寻找解的问题，这类问题可能会使用大得多的内存。几十年来，科学家们一直在思考，这两类是否实际上是同一回事，或者说，那个小小的笔记本对于更难的问题来说是否从根本上是不够用的。
哥伦比亚国立大学的一位研究人员现在提出了一项证明，论证这两类确实是不同的。由 J. Andres Montoya 领导的这项工作并不依赖于猜测或模拟，而是提供了一个严密的数学论证来分离这两个计算世界。该证明的核心在于对两种不同类型的计算机器进行巧妙的比较。一方面是内存非常有限的机器，作者展示了这些机器可以被建模为一种特定的自动机，它配备了少量的标记或“鹅卵石（pebbles）”，可以在纸带上放置这些标记以记住位置。另一方面是实时运行的机器，它们在信息到达时即时处理，没有停下来思考的奢侈。作者证明了实时机器是如此强大，以至于它们可以解决那些需要不断增加数量的鹅卵石才能解决的问题，这远远超过了有限内存机器的能力。
要理解这个论证，首先必须理解“鹅卵石层级（pebble hierarchy）”的概念。想象一台机器可以在一条长纸带上放置有限数量的标记，以帮助它导航。拥有一个标记时，机器可以解决一组特定的问题；拥有两个标记时，它可以解决更难的问题；拥有三个时，难度进一步提升。作者证明，能够用极少量内存解决的问题类，恰好等于所有能用任何有限数量的这些标记来解决的问题的集合。这创造了一个难度阶梯：随着你增加更多的标记，你就向上攀爬，解决更难的问题。作者随后引入了一个特定的、极其困难的问题，称为“最难的拟实时语言（hardest quasi-real-time language）”。这是一个实时机器可以解决的问题，它作为整个实时问题类的基准。
证明的关键在于展示这个最难的实时问题在基于标记的机器阶梯中处于如此高的位置，以至于任何有限数量的标记都无法触及。作者构建了一系列日益复杂的问题，每一个都比前一个更难，并证明对于你选择的任何固定的标记数量，序列中总会存在一个你的机器无法解决的问题。因为最难的实时问题属于这个序列，所以可以得出结论：没有任何一台拥有有限数量标记的机器能够解决它。由于有限内存机器等同于拥有有限数量标记的机器，因此最难的实时问题无法用有限的内存来解决。
这一发现具有深远的影响：能够用极少量内存解决的问题类，严格小于由实时机器解决的问题类。由于实时机器是更广泛的、可以用合理时间和内存解决的问题类的一个子集，这证明了极小内存类与较大的类是不同的。作者明确排除了这两类可能相同的可能性，拆解了“一个小笔记本足以应对所有高效计算”的观点。该证明利用了一种涉及“熵（entropy）”——一种衡量信息和不确定性的度量——的技术，来表明试图解决这些难题的机器其内部状态所包含的信息，必然比只能持有有限标记的机器所能持有的信息更多。
论文最后指出，这种分离不仅适用于所分析的具体类别，还为证明其他主要复杂度类也是截然不同的提供了一条路径。作者建议，类似的策略可以用来证明非确定性对数空间与非确定性多项式时间是不同的，甚至可能证明多项式时间与非确定性多项式时间是不同的。虽然论文的重点在于对数空间与非确定性多项式时间之间的分离，但其使用的方法——即展示一个问题类在机器能力层级中处于多么“高”的位置——为理解计算的根本极限提供了一个新的、强大的工具。这项工作是一个决定性的论证，证明某些问题本质上过于复杂，无论算法多么巧妙，都无法用极少的内存来解决。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。