В теории сложности и теории вычислимости машина -оракул — это абстрактная машина, используемая для изучения проблем принятия решений . Его можно представить как машину Тьюринга с черным ящиком , называемую оракулом , которая способна решать определенные задачи за одну операцию. Проблема может быть любого класса сложности . Можно использовать даже неразрешимые проблемы , такие как проблема остановки .
Машину-оракул можно представить как машину Тьюринга , соединенную с оракулом . В этом контексте оракул — это сущность, способная решить некоторую проблему, которая, например, может быть проблемой принятия решения или функциональной проблемой . Проблема не обязательно должна быть вычислимой; оракул не считается машиной Тьюринга или компьютерной программой. Оракул — это просто « черный ящик », способный найти решение для любого случая заданной вычислительной задачи:
Машина-оракул может выполнять все обычные операции машины Тьюринга, а также может запрашивать у оракула решение любого экземпляра вычислительной задачи для этого оракула. Например, если проблема представляет собой проблему решения для набора A натуральных чисел, оракул предоставляет оракулу натуральное число, и оракул отвечает «да» или «нет», указывая, является ли это число элементом A. .
Существует множество эквивалентных определений машин Тьюринга-оракулов, которые обсуждаются ниже. Представленный здесь материал принадлежит ван Мелкебеку (2003, стр. 43).
Машина-оракул, как и машина Тьюринга, включает в себя:
Помимо этих компонентов, машина-оракул также включает в себя:
Время от времени машина-оракул может переходить в состояние ASK. В этом случае за один вычислительный шаг выполняются следующие действия:
Таким образом, результатом перехода в состояние ASK является получение за один шаг решения экземпляра проблемы, записанного на ленте оракула.
Существует множество альтернативных определений приведенному выше. Многие из них специализированы для случаев, когда оракул решает проблему принятия решения. В этом случае:
Эти определения эквивалентны с точки зрения вычислимости по Тьюрингу: функция является оракулом-вычислимой по данному оракулу при всех этих определениях, если она оракул-вычислима при любом из них. Однако эти определения не эквивалентны с точки зрения вычислительной сложности. В целом требуется определение, подобное определению ван Мелькебека, с использованием ленты оракула, которая может иметь свой собственный алфавит.
Класс сложности задач решения , решаемых алгоритмом класса A с оракулом для языка L, называется AL . Например, P SAT — это класс задач, решаемых за полиномиальное время с помощью детерминированной машины Тьюринга с оракулом для булевой проблемы выполнимости . Обозначение A B можно расширить до набора языков B (или класса сложности B), используя следующее определение:
Когда язык L полон для некоторого класса B, тогда A L = AB при условии, что машины в A могут выполнять сокращения, используемые в определении полноты класса B. В частности, поскольку SAT является NP-полным относительно полиномиальных сокращений времени, П САТ = П НП . Однако если A = DLOGTIME , то A SAT может не равняться A NP . (Определение, данное выше, не является полностью стандартным. В некоторых контекстах, таких как доказательство теорем об иерархии времени и пространства , более полезно предположить, что класс, определяющий абстрактную машину, имеет доступ только к одному оракулу для одного языка. В этом контексте не определяется, если класс сложности не имеет каких-либо полных проблем в отношении сокращений, доступных для .)
Понятно, что NP ⊆ P NP , но вопрос о том, равны ли NP NP , P NP , NP и P, остается в лучшем случае экспериментальным. Считается, что они разные, и это приводит к определению полиномиальной иерархии .
Машины Oracle полезны для исследования взаимосвязи между классами сложности P и NP , рассматривая взаимосвязь между PA и NP A для оракула A. В частности, было показано, что существуют языки A и B такие, что PA = NP A. и P B ≠ NP B. [4] Тот факт, что вопрос P = NP релятивизирует оба пути, рассматривается как свидетельство того, что ответить на этот вопрос сложно, потому что метод доказательства, который делает релятивизирующий (т.е. на него не влияет добавление оракула), не ответит на вопрос P = NP. [5] Большинство методов доказательства являются релятивистскими. [6]
Можно рассмотреть случай, когда оракул выбирается случайным образом среди всех возможных оракулов (бесконечное множество). В этом случае было показано, что с вероятностью 1 PA ≠ NP A. [7] Когда вопрос верен почти для всех оракулов, говорят, что он верен для случайного оракула . Такой выбор терминологии оправдан тем фактом, что случайные оракулы поддерживают утверждение только с вероятностью 0 или 1. (Это следует из закона нуля–единицы Колмогорова .) Это лишь слабое доказательство того, что P≠NP, поскольку утверждение может быть истинным для случайного оракула, но ложным для обычных машин Тьюринга; [ оригинальное исследование? ] например, IP A ≠PSPACE A для случайного оракула A, но IP = PSPACE . [8]
Машина с оракулом для решения проблемы остановки может определить, остановятся ли отдельные машины Тьюринга на определенных входных данных, но она не может определить в целом, остановятся ли машины, эквивалентные ей самой. Это создает иерархию машин, каждая из которых имеет более мощный оракул остановки и еще более сложную проблему остановки. Эту иерархию машин можно использовать для определения арифметической иерархии . [9] [ нужна страница ]
В криптографии оракулы используются для аргументации безопасности криптографических протоколов, в которых используется хеш-функция . Снижение безопасности протокола дается в том случае, когда вместо хеш-функции случайный оракул отвечает на каждый запрос случайно, но последовательно; Предполагается, что оракул доступен всем сторонам, включая злоумышленника, как и хеш-функция. Такое доказательство показывает, что, если злоумышленник не решит сложную проблему, лежащую в основе снижения безопасности, он должен использовать какое-то интересное свойство хэш-функции, чтобы взломать протокол; они не могут рассматривать хэш-функцию как черный ящик (т.е. как случайный оракул).
