由于我们的主要目标是统一和关联前期工作中研究的几种不同模型,因此我们需要引入相当数量的计算模型。我们建议读者在阅读介绍时,手边要有图 10(最后一页)中的路线图,以便保持清晰的视野,并在需要时再次查阅本概述。我们从第 1.3 节开始我们的冒险,介绍图 10 最顶部的经典模型,然后将它们与第 1.4 节中的 LCL 当前格局联系起来。接下来,我们将在第 1.5 节中逐步研究量子以及有界依赖和非信号模型,之后我们将进行第一次休息。此时,我们熟悉了图 10 的上半部分,并准备在第 1.6 节中陈述与有限依赖过程的对称性破坏相关的第一个主要贡献。然后,在第 1.7 节中,我们将转向乍一看似乎完全不相关的模型。它们处理顺序、动态和在线设置中的局部性。然而,正如我们将在 1.8 节中看到的那样,我们可以将所有这些模型连接到一个层次结构中,看似正交的模型夹在确定性局部和随机在线局部之间,我们可以证明各种强有力的结果,将这两个极端之间的复杂性景观联系起来。
主要关键词