相对化背后的直觉

Question

我参加了计算复杂性的课程。我的问题是我不明白 相对方法. 。不幸的是，我试图在许多教科书中找到一些直觉，到目前为止没有成功。如果有人能够阐明这个话题，我将不胜感激，以便我能够独自继续。以下几个句子是问题，我对相对化的想法将有助于进行讨论。

相对化通常与对角线化相比，这是一种有助于区分可数集和无数集的方法。以某种方式来自相对化，$ p $对$ np $问题无法通过对角度解决。我真的没有看到为什么相对化表现出对角化的无用，如果没有用，为什么实际上是没有用的。

首先，Oracle Turing Machine $ M^a $背后的想法非常明确。但是，当涉及到$ np^a $和$ p^a $时，直觉消失了。 Oracle是一个专为特殊语言设计的黑框，回答了甲骨文输入的字符串是否在时间1中。正如我所理解的那样，包含Oracle的TM只是进行一些辅助操作并询问Oracle。因此，TM的核心是甲骨文，其他一切都不那么重要。 $ p^a $和$ np^a $之间有什么区别，甚至在两个时间1中都可以认为Oracle。

最后一件事是证明存在Oracle $ b $的存在，使$ p^b neq np^b $。我在几本教科书中找到了证据，在所有教科书中，证明似乎很模糊。我试图使用 Sipser的“复杂性简介”，第9章。顽固性, ，并且没有得到构建所有多项式时间oracle tms $ m_i $的想法。

这或多或少是我对相对化的所有知识，我将不胜感激是否会决定分享他/她对这个话题的想法。

附录: ：在其中一本教科书中，我找到了$ np^b $语言的示例（计算复杂性：Boaz Barak Sanjeev Arora的现代方法。定理3.7。第74页）。 $ u_b = left {1^n： space Length的某些 Space String Space Space N Space是 Space是 Space B right } $，它是一个Unary语言。我相信（1,11,11,11,1111，...）都在$ u_b $中。作者确认，这种语言在$ np^b $中，这是我不明白的，因此，b的oracle可以在时间上解决所有内容1.为什么我们需要甲骨文的非确定性TM。如果这不是$ NP^b $的好示例，请放置您，以批准存在$ np^b $。

Answer 1

您还没有真正问任何问题，但是似乎您不知道$ rm {p}^a $含义以及$ rm {np}^a $表示语言$ a $。类$ rm {np}^a $只是在“ np time”中可以决定的所有语言，给定带有$ a $作为oracle的图灵计算机。这意味着一台非确定性的Turing Machine，可以使用$ A $在多项式时间内运行。 $ rm {p}^a $是确定性版本。