Низкая (сложность) - Low (complexity)

В теория сложности вычислений, а язык B (или класс сложности B) называется низкий для класса сложности А (с некоторой разумной релятивизированной версией А) если АB = А; то есть, А с оракул за B равно А.[1] Такое утверждение означает, что абстрактная машина который решает проблемы в А не достигает дополнительной мощности, если ему дается возможность решать проблемы в B по себестоимости. В частности, это означает, что если B низкий для А тогда B содержится в А. Неформально низкое означает, что проблемы в B решаются не только машинами, которые могут решать проблемы в А, но их «легко решить». An А машина может имитировать множество запросов Oracle к B без превышения его ресурсов.

Результаты и отношения, которые делают один класс низким для другого, часто называют низость полученные результаты. Набор языков низкий для класса сложности А обозначается Низкий (А).

Низкие для себя классы

Известно, что несколько классов естественной сложности сами по себе невысоки. Такой класс иногда называют самоуничижительный.[2] Скотт Ааронсон называет такой класс класс физической сложности.[3] Обратите внимание: низкое самочувствие - более сильное условие, чем закрыт при дополнении. Неформально, низкий класс для самого себя означает, что проблема может использовать другие проблемы в классе в качестве подпрограмм с единичной стоимостью, не превышая мощности класса сложности.

Самостоятельно низкими известны следующие классы:[3]

  • п самоунижается (то есть Pп = P), потому что алгоритмы с полиномиальным временем закрываются относительно композиции: алгоритм с полиномиальным временем может выполнять полиномиальное количество запросов к другим алгоритмам с полиномиальным временем, сохраняя при этом полиномиальное время работы.
  • PSPACE (с ограниченным механизмом доступа оракула) также является самоуменьшающимся, и это можно установить точно таким же аргументом.
  • L Самостоятельно низкий, потому что он может имитировать запросы Oracle в пространстве журнала в пространстве журнала, повторно используя одно и то же пространство для каждого запроса.
  • NC также низко по той же причине.
  • BPP также является низким для самого себя, и те же аргументы почти работают для BPP, но нужно учитывать ошибки, что немного усложняет демонстрацию низкого BPP для самого себя.
  • Точно так же аргумент в пользу BPP почти проходит для BQP, но мы должны дополнительно показать, что квантовые запросы могут выполняться в когерентной суперпозиции.[4]
  • Обе Четность P () и BPP низки для себя. Это было важно для демонстрации Теорема Тоды.[5]
  • NP ∩ coNP низка для себя.[1]

Каждый низкий для себя класс закрывается под дополнять, при условии, что он достаточно мощный, чтобы отрицать логический результат. Отсюда следует, что НП не является низким для себя, если НП = со-НП, что считается маловероятным, поскольку подразумевает, что полиномиальная иерархия коллапсирует до первого уровня, тогда как широко распространено мнение, что иерархия бесконечна. Обратное к этому утверждению неверно. Если класс закрыт по дополнению, это не означает, что этот класс низок для себя. Примером такого класса является EXP, которая закрывается при дополнении, но не является низкой для себя.

Классы, низкие для других классов сложности

Некоторые из наиболее сложных и известных результатов относительно небольшого количества классов включают:

  • BQP низкий для PP [6] Другими словами, программа, основанная на принятии решения большинством неограниченного числа итераций поливремени. рандомизированный алгоритм может легко решить все проблемы, которые квантовый компьютер может решить эффективно.
  • В проблема изоморфизма графов низкий для Четность P ().[7] Это означает, что если мы можем определить, НП машина имеет четное или нечетное количество принимающих путей, мы можем легко решить изоморфизм графов. На самом деле, позже было показано, что изоморфизм графов низок для ЗППНП.[8]
  • Усиленный ПП низкий для PP.[9]
  • NP ∩ coNP равно множеству языков low для NP, то есть Low (NP) = NP ∩ coNP.[1]
  • AM ∩ coAM низкий для ZPPНП.[1]

Приложения

Слабость особенно ценна в аргументах релятивизации, где ее можно использовать для установления того, что мощность класса не меняется в «релятивизированной вселенной», где определенная машина-оракул доступна бесплатно. Это позволяет нам рассуждать об этом так же, как обычно. Например, в релятивизированной вселенной BQP, PP все еще закрыто относительно объединения и пересечения. Это также полезно при стремлении расширить возможности машины с помощью оракулов, потому что меньшие результаты определяют, когда мощность машины останется прежней.

Смотрите также

Рекомендации

  1. ^ а б c d Кёблер, Йоханнес; Торан, Якобо (2015). «Низкие результаты: следующее поколение». Бюллетень EATCS. 117.
  2. ^ Роте, Дж. (2006). Теория сложности и криптология: введение в криптосложность. Тексты по теоретической информатике. Серия EATCS. Springer Berlin Heidelberg. ISBN  978-3-540-28520-5. Получено 2017-05-15.
  3. ^ а б http://www.scottaaronson.com/blog/?p=2070#comment-282988
  4. ^ Бернштейн и Вазирани, Квантовая теория сложности, SIAM Журнал по вычислениям, 26(5):1411-1473, 1997. [1]
  5. ^ [2]
  6. ^ Л. Фортноу и Дж. Д. Роджерс. Ограничения сложности квантовых вычислений. В Труды IEEE Complexity '98С. 202-209. 1998 г. arXiv:cs.CC/9811023.
  7. ^ В. Арвинд и П. Курур. Изоморфизм графов находится в SPP. ECCC  TR02-037. 2002.
  8. ^ Викраман Арвинд и Йоханнес Кёблер. Низкий изоморфизм графов для ZPP (NP) и других результатов с низкой точностью. Материалы 17-го ежегодного симпозиума по теоретическим аспектам информатики, ISBN  3-540-67141-2, с.431-442. 2000 г.
  9. ^ Л. Ли. О счетных функциях. Докторская диссертация, Чикагский университет. 1993 г.