小复杂性类相对化理论：NL与NC1的分离与ACk相对化

小复杂性类的相对化理论探讨了在计算复杂性理论中，特别是在非确定性类（如NC1、NL、AC0(m)和TC0）以及它们之间的关系中的相对化概念。这个研究领域主要关注如何将复杂性理论中的经典问题和结构与更高级别的理论相比较，以便更好地理解它们的界限和可能的相互作用。 在本研究中，作者首先回顾了NC1类与线性代数的关系，特别是如何定义这些类的相对版本，例如L-。他们指出NL类并不在NC1L-中，这意味着NL与NC1的相对化版本之间存在差异。为了证明这一点，作者利用了Wilson的堆栈Oracle模型，这是一种模型，其中计算资源被限制在特定的Oracle访问模式下，如NC1电路中的预言机门的嵌套深度限制。 研究者们展示了两个W的坍缩现象，即AC0(m)、TC0、NC1、L-和NL之间的类之间的关系，表明某些类可以相对化到更低的复杂性层次。这在一定程度上扩展了之前关于相对化理论的理解，尤其是对ACk(α)这样的函数等级制度的处理，强调了嵌套预言门的有限性，即预言函数的构建不能超出某个固定的复杂度层次k。 此外，作者还改进和发展了描述P类子类的相对化理论，强调了一个函数在理论中的可证明性与其在相对化类中的地位紧密相关。神谕分离的概念在这里意味着，如果一个函数在相对化理论中被证明是不可证明的，那么它在原理论中的地位也将受到影响。这与传统的相对化方法不同，后者通常用于P和NP的分离，但在子类中寻找相对化版本则提供了新的洞察。 值得注意的是，尽管已经有一些关于NL和NC1的相对化尝试，例如允许图灵机在有Oracle查询的情况下工作的NL(α)，但这些并不是对所有相对化版本的完整覆盖。研究者指出，某些包含相对化的情况，如(1)中提到的NLAC1，可能并未完全涵盖所有可能的相对化结构。 小复杂性类的相对化理论是计算复杂性研究中的一个重要分支，它不仅提供了理解复杂性类之间相互关系的新视角，而且对于证明分离和坍缩结果具有潜在的应用价值。通过定义和分析这些相对化的概念，研究人员能够揭示出理论上的限制和可能性，进一步推动了复杂性理论的边界探索。