Интуиция за релятивизацией

10

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

Очень часто релятивизация сравнивается с диагонализацией, которая помогает различать счетное множество и неисчисляемое множество. Из релятивизации так или иначе вытекает, что вопрос против не может быть решен диагонализацией. Я действительно не вижу идеи, почему релятивизация показывает бесполезность диагонализации, и если она бесполезна, то почему на самом деле бесполезна.Н ПPNP

Идея машины Оракула Тьюринга на первый взгляд очень ясна. Однако, когда дело доходит до и интуиция исчезает. Oracle - это черный ящик, который предназначен для специального языка и отвечает на вопрос, есть ли строка на входе оракула на языке времени 1. Как я понял, TM, которая содержит оракула, просто делает некоторые вспомогательные операции и спрашивает оракула. Так что ядром ТМ является оракул, все остальное менее важно. В чем разница между и , даже мысль оракула в обоих из них работает во времени 1. Н П А П А П А Н П АMANPAPAPANPA

Последнее , что это доказывает существование оракула такой , что P ^ B \ NEQ NP ^ B . Я нашел доказательства в нескольких учебниках, и во всех них они кажутся очень расплывчатыми. Я попытался использовать «Введение в сложность» Sipser, глава 9. Непостижимость и не пришла в голову идея составления списка всех оракулов полиномиального времени М_и .P BN P BBPBNPBMi

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

Приложение : в одном из учебников я нашел пример языка («Вычислительная сложность: современный подход» Боаза Барака Санджеева Арора. Теорема 3.7. Страница 74). это унарный язык. Я считаю, что (1,11,111,1111, ...) все в . Автор утверждает, что такой язык есть в и я не могу понять, почему, следовательно, оракул для B может разрешить все вовремя 1. Зачем нам нужен недетерминированный TM с оракулом. Если это не хороший пример пожалуйста положите ваш таким образом, чтобы утвердить существование .У Б = { 1 н : с ö м E сек т т я н г о е л е н г т ч п я ев I п BNPBUB={1n:some string of length n is in B}UBNPBNPBNпВ

ком
источник
2
N P A AпA и - это классы языка, они не являются машинами Тьюринга. Вы говорите, что оракул является «ядром» ТМ, но это не обязательно так. Например, что если - пустой язык? NпAA
Юваль Фильмус
это очень сложная тема, как правило, не так много для студентов. один аспект заключается в том, что оракулы в некоторой степени зависят от модели. то есть, очевидно, нет строго последовательного способа разработки оракулов. основная интуиция заключается в том, что это машина с «магической» функцией подпрограммы (предоставленной оракулом), так что машина + оракул всегда, по крайней мере, так же мощна, как оригинальная машина, но иногда не значительно более мощна ...
vzn
1
связанный вопрос: cs.stackexchange.com/questions/1271/… , с отличным ответом от Цуёси Ито
А.Шульц
Я не уверен, что вы спрашиваете. Вы, кажется, не понимаете доказательства BGS, а также задаете кучу других вопросов. Пожалуйста, задайте один сфокусированный вопрос. Обратите внимание, что это не доска обсуждений или форум, это сайт вопросов и ответов.
Каве
Вы просите объяснить BGS доказательство существования оракула, который разделяет P и NP? Вы спрашиваете о связи релятивизации и диагонализации? (если да, отвечает ли ответ Цуёси в выложенном вопросе на ваш вопрос? если нет, объясните, почему нет.)
Kaveh

Ответы:

7

Вы на самом деле не спросил какой - либо вопрос, но мне кажется , что вы не знаете , что значит и в чем означает для языка . Класс - это просто все языки, которые разрешимы в "NP time", если использовать машину Тьюринга с оракуломЭто означает недетерминированную машину Тьюринга с доступом к которая работает за полиномиальное время. является детерминированной версией.пANпAANпAAAпA

Пол Г.Д.
источник
1
Большое спасибо за ответ, не могли бы вы привести пример того, как мощь NTM с Oracle позволяет нам распознавать больше языков, чем DTM с Oracle. BGS доказательство показывает такой язык, но я не получил доказательство.
ком
Иногда вместо языка я нахожу некоторый класс сложности, например , что это значит в этом случае? Что мы выбираем чтобы быть NP-завершенным? (в более общем смысле, что мы выбираем полный язык для класса )? P N P A AAпNпAA
Fawzy Hegab
пNпп