为什么相对化是一个障碍？

Question

当我解释 Baker-Gill-Solovay 证明时，存在一个我们可以拥有的预言机 $\mathsf{P} = \mathsf{NP}$，以及一个我们可以拥有 $\mathsf{P} 的预言机 eq \mathsf{NP}$ 给一个朋友，有人提出一个问题，为什么这种技术不适合证明 $\mathsf{P} eq \mathsf{NP}$ 问题，我无法给出一个满意的答复。

更具体地说，如果我有一种方法可以证明 $\mathsf{P} eq \mathsf{NP}$ 并且如果我可以构造预言机来使上述情况发生，为什么它会使我的方法无效？

关于这个主题有什么解释/想法吗？

Answer 1

更具体地说，如果我有一个方法来证明 P≠NP，并且如果我可以构建预言机来实现上述情况，为什么我的方法会无效呢？

请注意，后面的“如果”不是条件，因为 Baker、Gill 和 Solovay 已经构建了这样的预言机。这只是一个数学真理：(1) 存在一个相对于 P=NP 的预言，(2) 存在一个相对于 P≠NP 的预言。

这意味着，如果你有一种方法来证明 P≠NP，并且相同的证明同样可以证明更强的结果“P^A≠NP^A 对于所有预言机 A，”那么你的方法注定会失败，因为它与（1）相矛盾。

换句话说，证明 P≠NP 和证明例如时间层次定理，因为后者的证明只是使用对角化，并且同样适用于任何相对化世界。

当然，这并不意味着P≠NP没有证据。这样的证明（如果存在的话）必定无法证明上述更强的结果。换句话说，证明的某些部分必须区分非相对化世界和任意相对化世界。

Answer 2

已经有好的答案，但是我想添加一些小点。

假设我们有一种解决问题的技术，例如 对角度. 。假设我们要证明该技术无法解决特定问题 $ mathsf {p} $ vs. $ mathsf {np} $. 。如何显示？

在进行进一步之前，请注意，像对角线化的技术在这里不是正式的概念（尽管我们可以这样做）。此外，该技术无法本身无法解决该问题的事实并不意味着它在解决问题上根本没有用，我们也许能够对其进行修改和/或将其与其他技术相结合以解决问题。

现在，让我们回到问题。一种表明技术无法解决特定问题的方法是，如果它可以在解决另一个问题的另一个框架中也可以使用，而在这种情况下我们会得到的答案将是错误的。这就是在这里发生的事情。如果对角度可以从$ mathsf {p} $分开$ mathsf {np} $，则可以使用同一参数将所有参数用于分离$ mathsf {np^a} $从$ mathsf {p^a} $分离$ a $。但是我们知道有一个甲骨文，所以这是错误的（以任何$ mathsf {pspace} $为oracle作为Oracle）。因此，对角不能将$ mathsf {np} $与$ mathsf {p} $分开。

这个论点的要点是一种 转移原理:

我们可以将无甲骨文的TMS的对角参数传输到带有Oracles的TMS。

在这里这是可能的，因为对角论证是基于 模拟 此外，模拟并不取决于机器的内部，而仅取决于这些仿真的最终答案。这种对角度称为 简单的对角度. 。在模拟中，机器的工作原理都没关系，我们只关心机器的最终答案。添加甲骨文不会改变这一点，因此仿真和参数也将在我们拥有Oracles的框架中起作用。

更正式的是，我们可以将对角度参数视为来自一类机器的函数（例如$ Mathsf {p} $），以显示机器无法解决问题（例如$ SAT $）。此反例函数是对角函数。对角度化是简单的，如果它给出的反例不取决于机器的内部，即如果两个多项式时间DTM具有相同的语言，则反例显示它们无法求解对角度化功能给出的$ SAT $是相同的。

您可能想知道这是否是一个很大的限制？为什么反例需要取决于机器的内部结构？我们可以使用无法使用简单的对角线化证明的对角度证明分离？答案是肯定的。实际上，Kozen在他的1978年论文中显示了“子销售类的索引”（BGS结果后3年），如果$ mathsf {np} $可以与$ mathsf {p} $分开。实际上，已经发现了这样的论点。例如，Fortnow和Van Melkebeek的SAT时空间较低（2000）使用一种称为的技术 间接对角线 这给出了非简单的对角度化。

那么，对对角线化无法解决$ Mathsf {p} $ vs. $ Mathsf {np} $不正确的说法吗？好吧，总的来说，专家在这里对对角线的含义是 简单的对角度 这是有充分理由的。

一般的对角度论点是如此一般，以至于将它们称为技术并没有多大意义，您可以轻松地将任何分离参数转变为对角线化参数而没有太多洞察力：如果我们已经有了某种分离两个复杂性类别的方法，那么我们可以在较大的类中选择一个功能，而不是在较小的类中。在较小的班级中列出机器的任何枚举。令$ m $为枚举中的任何机器。我们必须定义$ m $的反例。但是我们已经知道$ m $无法解决问题，所以 存在 实例显示了这一点，将对角度函数的值定义为$ m $。如果您想查看详细信息，请查看Kozen的论文，这是一个大图片的视图。

夏季：

• 当专家说“对角度无法解决$ mathsf {p} $ vs. $ mathsf {np} $“他们的意思是”简单的 对角无法解决$ Mathsf {p} $ vs. $ Mathsf {np} $“不是一般的。
• 简单的对角度无法从$ mathsf {p} $将$ mathsf {np} $分开的原因是，它是用oracles转移到框架的（在文献中，它被称为“对角相关化”），而分离则不能保持。
• 从Oracle的框架转移到Oracles Works的框架的原因是，简单的对角化是基于TMS的黑框模拟，并且机器的工作原理都无关紧要，无论是否具有Oracle。

两篇有关对角化的信息的好论文是

• 兰斯·福特诺（Lance Fortnow）的调查论文“对角色”，2001年和
• 拉塞尔（Russell Impagliazzo），情人节（Valentine Kabanets）和安东尼娜·科洛科洛娃（Antonina Kolokolova 代数化 是 简单的对角度.)

Answer 3

令$ mathrm {a} $和$ mathrm {b} $为两个复杂性类。分离（$ mathrm {a} neq mathrm {b} $）或倒塌（$ mathrm {a} = mathrm {b} $），如果所有Oracles $ Mathrm {O} $ {O} $我们有$ mathrm {a}^ mathrm {o} neq neq mathrm {b}^ mathrm {o} $} $或$ mathrm {a}^ mathrm {o} {o} $。 Baker-Gill-Solovay证明告诉我们，$ P = NP $或$ P neq NP $不相对。

为什么这是个问题？当此证明出来时，我们知道将大多数技术和技巧分开或崩溃的复杂性类“相对化”，因为它们与任何甲骨文有关。例如，时间层次定理（以及它的空间和非确定版本）“相对启动”：它们证明了这种分离相关的类别的分离，实际上，它们证明了分离对分离的较强的结果，相对于分离有相对的结果。任何Oracle。

如果技术或技巧不管是否存在甲骨文，则无法通过上述参数证明$ p = np $或$ p neq np $。这意味着我们知道的许多技巧和技术都不适用于这个问题（或实际上在许多开放问题上）。您还可以将其用作任何声称的$ p neq np $证明的理智检查：检查这个想法是否在存在$ mathrm {pspace} $的存在下是否无法保持是错的。