Совет (сложность)
В теории сложности вычислений строка совета — это дополнительный ввод в машину Тьюринга , который может зависеть от длины n ввода, но не от самого ввода. Проблема решения относится к классу сложности P/ f ( n ), если существует машина Тьюринга M с полиномиальным временем , обладающая следующим свойством: для любого n существует рекомендательная строка A длины f ( n ), такая что для любого входного сигнала x длины n машина M правильно решает задачу на входе x при данных x и A. ,
Самый распространенный класс сложности, включающий советы, — это P/poly , где длина совета f ( n ) может быть любым полиномом от n . P/poly равен классу задач решения, в котором для каждого n существует булева схема полиномиального размера , правильно решающая задачу на всех входных данных длины n . Одно направление эквивалентности легко увидеть. Если для каждого n существует булева схема A ( n ) полиномиального размера, решающая задачу, мы можем использовать машину Тьюринга, которая интерпретирует строку совета как описание схемы. Тогда, учитывая описание A ( n ) в качестве совета, машина правильно решит задачу на всех входных данных длины n . Другое направление использует моделирование машины Тьюринга с полиномиальным временем с помощью схемы полиномиального размера, как в одном доказательстве теоремы Кука . Моделировать машину Тьюринга с помощью советов не сложнее, чем моделировать обычную машину, поскольку строку совета можно включить в схему. [1]
Из-за этой эквивалентности P/poly иногда определяют как класс проблем принятия решений, решаемых с помощью булевых схем полиномиального размера или неоднородных логических схем полиномиального размера.
P/poly содержит как P , так и BPP (теорема Адлемана). Он также содержит некоторые неразрешимые проблемы, такие как унарная версия каждой неразрешимой проблемы, включая проблему остановки . По этой причине он не содержится в DTIME ( f ( n )) или NTIME ( f ( n )) ни для одного f .
Классы советов могут быть определены для других границ ресурсов вместо P . Например, взяв недетерминированную машину Тьюринга с полиномиальным временем и советом длины f ( n ), мы получим класс сложности NP / f ( n ) . Если нам разрешен совет длиной 2 н каждый ввод длины n , мы можем использовать его для кодирования того, содержится ли в языке . Следовательно, любая булева функция вычислима с советом длины 2. н и советы более чем экспоненциальной длины не имеют смысла.
Аналогично, класс L/poly можно определить как детерминированное лог-пространство с полиномиальным количеством советов.
Известные результаты включают в себя:
- Классы NL/poly и UL/poly одинаковы, т.е. недетерминированные вычисления логарифмического пространства с советами могут быть сделаны однозначными. [2] Это можно доказать с помощью леммы об изоляции . [3]
- Известно, что coNEXP содержится в NEXP/poly . [4]
- Если NP содержится в P/poly , то полиномиальная временная иерархия рушится ( теорема Карпа-Липтона ).
Ссылки
[ редактировать ]- ^ Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, стр. 113, ISBN 9780521424264 , Збл 1193,68112 .
- ^ Рейнхардт, Клаус; Аллендер, Эрик (2000). «Сделать недетерминизм однозначным». СИАМ Дж. Компьютер . 29 (4): 1118–1131. CiteSeerX 10.1.1.55.3203 . дои : 10.1137/S0097539798339041 . Збл 0947.68063 .
- ^ Хемаспаандра, Лейн А.; Огихара, Мицунори (2002). Компаньон по теории сложности . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN 3-540-67419-5 . Збл 0993.68042 .
- ↑ Лэнс Фортноу , Маленькая теорема. Архивировано 5 августа 2019 г. в Wayback Machine.