Совет (сложность) - Advice (complexity)

В теория сложности вычислений, строка совета является дополнительным входом в Машина Тьюринга что может зависеть от длины п входа, но не самого входа. А проблема решения находится в класс сложности П/ж(п) если существует полиномиальная машина Тьюринга M со следующим свойством: для любого п, есть строка совета А длины ж(п) такой, что для любого входа Икс длины п, машина M правильно решает проблему на входе Икс, данный Икс и А.

Самый распространенный класс сложности, включающий советы, - это П / поли где длина совета ж(п) может быть любым полиномом от п. П / поли совпадает с классом задач решения таких, что для каждого п, существует полиномиальный размер Логическая схема правильно решая задачу на всех входах длины п. Одно направление эквивалентности легко увидеть. Если для каждого п, существует логическая схема полиномиального размера А(п) Решая проблему, мы можем использовать машину Тьюринга, которая интерпретирует строку совета как описание схемы. Тогда, учитывая описание А(п) как совет, машина правильно решит проблему на всех входах длины п. Другое направление использует моделирование машины Тьюринга с полиномиальным временем с помощью схемы с полиномиальным размером, как в одном из доказательств Теорема Кука. Моделирование машины Тьюринга с помощью совета не сложнее, чем моделирование обычной машины, поскольку строку совета можно включить в схему.[1]

Из-за этой эквивалентности П / поли иногда определяется как класс задач принятия решений, решаемых с помощью логических схем полиномиального размера или неоднородный размер полинома Булевы схемы.

П / поли содержит оба п и BPP (Теорема Адлемана). Он также содержит некоторые неразрешимый проблемы, такие как унарная версия каждой неразрешимой проблемы, включая проблема остановки. По этой причине он не содержится в DTIME (ж(п)) или NTIME (ж(п)) для любого ж.

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

Аналогично класс L / поли можно определить как детерминированное пространство журнала с полиномиальным количеством советов.

Известные результаты включают:

  • Классы NL / поли и UL / поли одинаковы, т.е. недетерминированное вычисление логарифмического пространства с советом может быть сделано однозначным.[2] Это можно доказать с помощью лемма об изоляции.[3]
  • Известно, что coNEXP содержится в NEXP / поли.[4]
  • Если НП содержится в П / поли, то иерархия полиномиального времени схлопывается (Теорема Карпа-Липтона ).

использованная литература

  1. ^ Арора, Санджив; Варак, Вооз (2009), Вычислительная сложность: современный подход, Cambridge University Press, стр. 113, ISBN  9780521424264, Zbl  1193.68112.
  2. ^ Рейнхардт, Клаус; Аллендер, Эрик (2000). «Сделать недетерминизм однозначным». SIAM J. Comput. 29 (4): 1118–1131. CiteSeerX  10.1.1.55.3203. Дои:10.1137 / S0097539798339041. Zbl  0947.68063.
  3. ^ Hemaspaandra, Lane A .; Огихара, Мицунори (2002). Товарищ по теории сложности. Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag. ISBN  3-540-67419-5. Zbl  0993.68042.
  4. ^ Лэнс Фортноу, Маленькая теорема