Схемы с оракулами против машин Тьюринга с оракулами

Проще говоря: как соотносятся машины Тьюринга с оракулами и семействами однородных цепей с оракулами? Как последние определяются для получения той же вычислительной модели для данной машины оракула Тьюринга?

Это может быть элементарный вопрос, но не очевидно, где искать, и я из тех людей, которым нравится следить за тем, чтобы в моих фондах использовался качественный раствор. Если есть стандартная ссылка, пожалуйста, укажите мне на это. (Книга Пападимитрия, например, похоже, вообще не описывает схемы с оракулами.)

Моя рабочая гипотеза заключается в следующем: единое семейство цепей с доступом к оракулу (например, для решения NP-полной задачи) определяется следующим образом:

Один определяет бесконечное семейство «ворот оракула» O _n , по одному для каждого размера схемы n, каждый из которых вычисляет функцию f _n : {0,1} ^cn → {0,1} для некоторой константы c.
Функции f _n, вычисленные воротами оракула O _n, должны быть «равномерными» в следующем смысле: для любых n <N и x ∈ {0,1} ⁿ нам требуется f _n ( x ) = f _N (0 ^{c ( N-n)} x ) --- то есть врата оракула должны использовать согласованную и расширяемую "кодировку" своих входов.
Затем определяется единообразное семейство цепей, где врата оракула входят в число разрешенных операций для схемы, ограничивая схему размером входного сигнала n для использования затвора O _n .

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

cc.complexity-theory turing-machines oracles circuit-families Ниль де Бодрап
источник

Поскольку я знаю, что вы работаете с квантовой информацией, я бы порекомендовал обзор Джона Уотроуса о сложности квантовых вычислений, где он также рассказывает о оракулах в квантовых цепях и запросах оракула в суперпозиции.

Робин Котари

Watrous 'статья также хорошая ссылка. Но в этом случае мне нужно было как-то не принимать идею о том, что кто-то захочет определить семейство релятивизированных цепей так, чтобы это не соответствовало простому тестированию одного и того же предиката для разных конечных длин строк. Напомним, что семантика оракула классически заключается в указании принадлежности к некоторому набору. Как оказалось, чертежи схемных ворот с символами «∈A?» на них было все что мне нужно.

Ниль де Бодрап

Ответы:

Лучшим справочником по релятивизированным цепям является статья Криса Уилсона «Relativized NC» http://www.springerlink.com/content/u727654246wu8662/

Второе условие, которое у вас есть (нисходящее закрытие O_n), не требуется для получения эквивалентности, скажем, между P ^ O и унифицированными многоразмерными цепями с оракулом O. Также ваше третье условие должно быть отброшено, размер схемы будет препятствовать доступу до O_m для м больше, чем размер цепи.

Лэнс Фортноу
источник

В статье Уилсона нет явных комментариев по поводу самих ворот оракула; но в ретроспективе, если вы серьезно относитесь к оракулу как к представлению членства в наборе логических строк, как в случае с ТМ, то мое второе условие просто не проблема (то есть само собой разумеется). При вашем наблюдении за излишним моим третьим условием, тогда достаточно иметь бесконечное семейство вентилей, которые определяют членство в A для любого конкретного конечного размера строки. Это подходит для меня; Хотел бы я подумать об этом раньше.

Ниль де Бодрап

Замечания в пользу случайных зрителей. Статья Уилсона определяет вклад глубины оракулов в k бит, которые должны быть записаны (log k), в очевидной аналогии с предыдущей работой Кука («Таксономия проблем с быстрыми параллельными алгоритмами»). , Информ. И Контроль, 64). Существует техническая проблема, разрешать ли запросы оракула в процессе построения самих схем (каждый из которых может также использовать оракулы): он комментирует, что это не имеет значения. В конце концов, однако, он недоволен существованием A, для которого NC_1 ^ A не содержится в NSPACE ^ A (O (n ^ k)), для любой константы k.

Ниль де Боудрап