Интуиция, лежащая в основе релятивизации

Question

Я прохожу курс по вычислительной сложности.Моя проблема в том, что я не понимаю Метод релятивизации.Я пытался найти немного интуиции во многих учебниках, но, к сожалению, пока безуспешно.Я буду признателен, если кто-нибудь прольет свет на эту тему, чтобы я мог продолжить самостоятельно.Несколько следующих предложений представляют собой вопросы и мои мысли о релятивизации, они помогут сориентироваться в дискуссии.

Очень часто релятивизацию сравнивают с диагонализацией, которая представляет собой метод, помогающий различать счетное множество и несчетное множество.Каким-то образом из релятивизации вытекает, что вопрос о $P$ и $NP$ не может быть решен путем диагонализации.Я действительно не понимаю, почему релятивизация показывает бесполезность диагонализации, и если она бесполезна, то почему она на самом деле бесполезна.

Идея машины Тьюринга-оракула $M^A$ на первый взгляд очень ясна.Однако когда дело доходит до $NP^A$ и $P^A$, интуиция пропадает.Oracle — это черный ящик, предназначенный для специального языка и отвечающий на вопрос, находится ли строка на входе оракула на языке за время 1.Насколько я понял, ТМ, содержащая оракула, просто выполняет некоторые вспомогательные операции и задает вопросы оракулу.Итак, ядром ТМ является оракул, все остальное менее важно.В чем разница между $P^A$ и $NP^A$, хотя оракул в обоих случаях работает за время 1.

Последнее, что нужно сделать, это доказать существование оракула $B$ такого, что $P^B eq NP^B$.Я нашел доказательство в нескольких учебниках, и во всех оно кажется очень расплывчатым.Я пытался использовать «Введение в сложность» Сипсера, глава 9.несговорчивость, и не пришла в голову идея построения списка всех ТМ оракула с полиномиальным временем $M_i$.

Это более или менее все, что я знаю о релятивизации, буду признателен, если кто-нибудь решит поделиться своими мыслями по этой теме.

Приложение:в одном из учебников я нашел пример языка $NP^B$ (вычислительная сложность:Современный подход Боаз Барак Санджив Арора.Теорема 3.7.стр. 74).$U_B=\left \{ 1^n:some \space string \space of \space length \space n \space is \space in \space B ight \} $ это унарный язык.Я считаю, что (1,11,111,1111,...) все находятся в $U_B$.Автор утверждает, что такой язык находится в $NP^B$, но я не могу понять почему, следовательно, оракул для B может решить все за время 1.Зачем нам недетерминированная ТМ с оракулом.Если это нехороший пример $NP^B$, пожалуйста, поставьте свой так, чтобы подтвердить существование $NP^B$.

Answer 1

На самом деле вы не задали ни одного вопроса, но, похоже, вы не знаете, что означает $ m{P}^A$ и что означает $ m{NP}^A$ для языка $A$.Класс $ m{NP}^A$ — это просто все языки, разрешимые за «NP-время», с учетом машины Тьюринга с $A$ в качестве оракула.Это означает недетерминированную машину Тьюринга с доступом к $A$, которая работает за полиномиальное время.$ m{P}^A$ — детерминированная версия.