Низкая (сложность)
В теории сложности вычислений язык ) , B (или класс сложности B ) называется низким для класса сложности A (с некоторой разумной релятивизированной версией A если A Б = А ; есть A с оракулом для B равно A. то [1] Такое утверждение подразумевает, что абстрактная машина , решающая проблемы в A, не получит дополнительной мощности, если ей будет предоставлена возможность решать проблемы в B по цене единицы продукции. В частности, это означает, что если B является низким для A то B содержится в A. , Неформально «низость» означает, что проблемы в B не только решаются машинами, которые могут решать проблемы в A , но и «легко решаются». Машина A может имитировать множество запросов оракула к B, не выходя за пределы своих ресурсов.
Результаты и отношения, которые устанавливают один класс как низкий по отношению к другому, часто называют результатами низкого уровня . Множество языков low для класса сложности A обозначается Low(A) .
Занятия низкие для себя
[ редактировать ]Известно, что некоторые классы естественной сложности сами по себе являются низкими. Такой класс иногда называют самонизким . [2] Скотт Ааронсон называет такой класс классом физической сложности . [3] Обратите внимание, что самонизкость является более сильным условием, чем закрытость при дополнении . Неформально, низкий для себя класс означает, что задача может использовать другие задачи в классе в качестве подпрограмм с удельной стоимостью, не превышая мощности класса сложности.
Известно, что следующие классы являются самонизкими: [3]
- P является самонизким (т.е. P П = P), поскольку алгоритмы с полиномиальным временем закрыты относительно композиции: алгоритм с полиномиальным временем может выполнять полиномиальное количество запросов к другим алгоритмам с полиномиальным временем, сохраняя при этом полиномиальное время работы.
- PSPACE (с механизмом ограниченного доступа Oracle) также является самонизким, и это может быть установлено точно таким же аргументом.
- L является самонизким, поскольку он может имитировать запросы оракула в пространстве журнала, повторно используя одно и то же пространство для каждого запроса.
- По той же причине NC также является самонизким.
- ZPP также низок сам по себе, и те же аргументы почти работают для BPP , но необходимо учитывать ошибки, что немного усложняет доказательство того, что BPP низок для самого себя.
- Аналогично, аргумент в пользу BPP почти проходит и для BQP , но нам нужно дополнительно показать, что квантовые запросы могут выполняться в когерентной суперпозиции. [4]
- Обе четности P ( ) и BPP сами по себе низкие. Они сыграли важную роль в доказательстве теоремы Тоды . [5]
- NP ∩ coNP сам по себе низок. [1]
Каждый класс, который является младшим для себя, закрывается с помощью комплемента , при условии, что он достаточно мощный, чтобы отрицать логический результат. Это означает, что NP не является низким для самого себя, если только NP = co-NP , что считается маловероятным, поскольку подразумевает, что полиномиальная иерархия схлопывается до первого уровня, тогда как широко распространено мнение, что иерархия бесконечна. Обратное к этому утверждению неверно. Если класс закрыт по дополнению, это не означает, что класс низок сам по себе. Примером такого класса является EXP , который закрыт при дополнении, но не является низким сам по себе.
Классы, низкие для других классов сложности
[ редактировать ]Некоторые из наиболее сложных и известных результатов относительно низкого уровня классов включают:
- BQP низкий для PP [6] Другими словами, программа, основанная на принятии решения большинства из неограниченного числа итераций многовременного рандомизированного алгоритма, может легко решить все проблемы, которые может эффективно решить квантовый компьютер .
- Проблема изоморфизма графов является низкой для четности P ( ). [7] Это означает, что если мы сможем определить, имеет ли NP- машина четное или нечетное количество принимающих путей, мы сможем легко решить изоморфизм графов. Фактически, позже было показано, что изоморфизм графов низок для ZPP. НАПРИМЕР . [8]
- Усиленный ПП низкий для ПП . [9]
- NP ∩ coNP равно множеству языков low для NP, т. е. Low(NP) = NP ∩ coNP. [1]
- AM ∩ coAM низкий для ZPP НАПРИМЕР . [1]
Приложения
[ редактировать ]Низкость особенно ценна в аргументах относительно релятивизации, где ее можно использовать для установления того, что мощность класса не меняется в «релятивизированной вселенной», где конкретная машина-оракул доступна бесплатно. Это позволяет нам рассуждать об этом так же, как обычно. Например, в релятивизированной вселенной PP BQP все еще замкнут при объединении и пересечении. Это также полезно при попытке расширить мощность машины с помощью оракулов, поскольку результаты низкого уровня определяют, когда мощность машины останется прежней.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с д Кёблер, Йоханнес; Торан, Хакобо (2015). «Результаты малости: следующее поколение». Бюллетень ЕАТКС . 117 .
- ^ Роте, Дж. (2006). Теория сложности и криптология: введение в криптосложность . Тексты по теоретической информатике. Серия EATCS. Шпрингер Берлин Гейдельберг. ISBN 978-3-540-28520-5 . Проверено 15 мая 2017 г.
- ^ Jump up to: Перейти обратно: а б «Линза вычислений в науках» . 25 ноября 2014 г. Архивировано из оригинала 6 мая 2021 г. Проверено 17 октября 2021 г.
- ^ Бернштейн и Вазирани, Теория квантовой сложности, SIAM Journal on Computing , 26(5):1411-1473, 1997. [1] Архивировано 25 мая 2011 г. в Wayback Machine.
- ^ «Архивная копия» (PDF) . Архивировано (PDF) из оригинала 06 мая 2021 г. Проверено 17 октября 2021 г.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ Л. Фортноу и Дж. Д. Роджерс. Ограничения сложности квантовых вычислений. В Proceedings of IEEE Complexity '98 , стр. 202-209. 1998. arXiv : cs.CC/9811023 .
- ^ В. Арвинд и П. Курур. Изоморфизм графов есть в SPP. ЕССС ТР02-037 . 2002.
- ^ Викраман Арвинд и Йоханнес Кёблер. Изоморфизм графов низкий для ZPP(NP) и других результатов низкой точности. Материалы 17-го ежегодного симпозиума по теоретическим аспектам информатики , ISBN 3-540-67141-2 , стр. 431-442. 2000.
- ^ Л. Ли. О счетных функциях. Докторская диссертация, Чикагский университет. 1993.