Я беру курс по вычислительной сложности. Моя проблема в том, что я не понимаю метод релятивизации . К сожалению, во многих учебниках я пытался найти немного интуиции, но пока безуспешно. Буду признателен, если кто-нибудь сможет пролить свет на эту тему, чтобы я смог продолжить сам. Несколько следующих предложений - это вопросы и мои мысли о релятивизации, они помогут ориентироваться в дискуссии.
Очень часто релятивизация сравнивается с диагонализацией, которая помогает различать счетное множество и неисчисляемое множество. Из релятивизации так или иначе вытекает, что вопрос против не может быть решен диагонализацией. Я действительно не вижу идеи, почему релятивизация показывает бесполезность диагонализации, и если она бесполезна, то почему на самом деле бесполезна.Н П
Идея машины Оракула Тьюринга на первый взгляд очень ясна. Однако, когда дело доходит до и интуиция исчезает. Oracle - это черный ящик, который предназначен для специального языка и отвечает на вопрос, есть ли строка на входе оракула на языке времени 1. Как я понял, TM, которая содержит оракула, просто делает некоторые вспомогательные операции и спрашивает оракула. Так что ядром ТМ является оракул, все остальное менее важно. В чем разница между и , даже мысль оракула в обоих из них работает во времени 1. Н П А П А П А Н П А
Последнее , что это доказывает существование оракула такой , что P ^ B \ NEQ NP ^ B . Я нашел доказательства в нескольких учебниках, и во всех них они кажутся очень расплывчатыми. Я попытался использовать «Введение в сложность» Sipser, глава 9. Непостижимость и не пришла в голову идея составления списка всех оракулов полиномиального времени М_и .P B ≠ N P B
Это более или менее все, что я знаю о релятивизации, я буду признателен, если кто-нибудь решит поделиться своими мыслями по этой теме.
Приложение : в одном из учебников я нашел пример языка («Вычислительная сложность: современный подход» Боаза Барака Санджеева Арора. Теорема 3.7. Страница 74). это унарный язык. Я считаю, что (1,11,111,1111, ...) все в . Автор утверждает, что такой язык есть в и я не могу понять, почему, следовательно, оракул для B может разрешить все вовремя 1. Зачем нам нужен недетерминированный TM с оракулом. Если это не хороший пример пожалуйста положите ваш таким образом, чтобы утвердить существование .У Б = { 1 н : с ö м E сек т т я н г о е л е н г т ч п я ев I п B
Ответы:
Вы на самом деле не спросил какой - либо вопрос, но мне кажется , что вы не знаете , что значит и в чем означает для языка . Класс - это просто все языки, которые разрешимы в "NP time", если использовать машину Тьюринга с оракуломЭто означает недетерминированную машину Тьюринга с доступом к которая работает за полиномиальное время. является детерминированной версией.пA Н ПA A Н ПA A A пA
источник