Введение

Абстрактная машина, используемая для изучения задач о решимости, вычислительное оборудование, продаваемое корпорацией Oracle. В теории сложности и теории вычислимости машина с оракулом — это абстрактная машина, используемая для изучения задач о решимости. Её можно представить как машину Тьюринга с «чёрным ящиком», называемым оракулом, который способен решать определённые задачи за одну операцию. Задача может относиться к любому классу сложности. Можно использовать даже неразрешимые задачи, такие как проблема останова.

Оракулы

Машина-оракул может быть представлена как машина Тьюринга, подключенная к оракулу. Оракул, в этом контексте, – это сущность, способная решать некоторую задачу, которая, например, может быть задачей принятия решения или задачей вычисления функции. Задача не обязательно должна быть вычислимой; не предполагается, что оракул является машиной Тьюринга или компьютерной программой. Оракул – это просто "черный ящик", способный выдать решение для любого экземпляра заданной вычислительной задачи: задача принятия решения представляется как множество A натуральных чисел (или строк). Экземпляр задачи – это произвольное натуральное число (или строка). Решение экземпляра – "ДА", если число (строка) принадлежит множеству, и "НЕТ" в противном случае. Задача вычисления функции представляется функцией f, отображающей натуральные числа (или строки) в натуральные числа (или строки). Экземпляр задачи – это вход x для f. Решение – значение f(x). Машина-оракул может выполнять все обычные операции машины Тьюринга, а также может обращаться к оракулу для получения решения любого экземпляра вычислительной задачи, для которой предназначен этот оракул. Например, если задача – это задача принятия решения для множества A натуральных чисел, машина-оракул предоставляет оракулу натуральное число, а оракул отвечает "да" или "нет", указывая, является ли это число элементом A.

Альтернативные определения

Существует множество альтернативных определений, отличных от приведенного выше. Многие из них специализированы для случая, когда оракул решает задачу принятия решения. В этом случае:
Некоторые определения, вместо записи ответа на оракульную ленту, имеют два специальных состояния YES и NO в дополнение к состоянию ASK. Когда к оракулу обращаются, следующее состояние выбирается как YES, если содержимое оракульной ленты содержится в оракульном множестве, и как NO, если содержимое в оракульном множестве отсутствует. Некоторые определения обходятся без отдельной оракульной ленты. Когда вводится состояние оракула, указывается символ ленты. Оракул запрашивается о количестве вхождений этого символа ленты на рабочей ленте. Если это число содержится в оракульном множестве, следующим состоянием является состояние YES; в противном случае – состояние NO. Другое альтернативное определение делает оракульную ленту доступной только для чтения и полностью исключает состояния ASK и RESPONSE. Перед запуском машины индикаторная функция оракульного множества записывается на оракульную ленту с использованием символов 0 и 1. Затем машина может запросить оракул, перейдя к нужной ячейке на оракульной ленте и прочитав там расположенное значение. Эти определения эквивалентны с точки зрения вычислимости по Тьюрингу: функция является оракульно вычислимой от данного оракула по всем этим определениям, если она оракульно вычислима по любому из них. Однако с точки зрения вычислительной сложности эти определения не эквивалентны. В общем случае требуется определение, подобное определению ван Мелкебека, использующее оракульную ленту, которая может иметь свой собственный алфавит.

Классы сложности оракульных машин

Класс сложности задач, разрешимых алгоритмом класса А с оракулом для языка L, называется AL. Например, PSAT – это класс задач, разрешимых за полиномиальное время детерминированной машиной Тьюринга с оракулом для задачи булевой выполнимости. Обозначение AB может быть расширено на множество языков B (или класс сложности B) с использованием следующего определения:

Когда язык L является полным для некоторого класса B, то AL=AB при условии, что машины в A могут выполнять редукции, используемые в определении полноты класса B. В частности, поскольку SAT NP-полный по отношению к полиномиальным редукциям, PSAT=PNP. Однако, если A = DLOGTIME, то ASAT может не равняться ANP. (Приведенное выше определение не является полностью стандартным. В некоторых контекстах, таких как доказательство теорем об иерархии времени и пространства, полезнее предположить, что абстрактная машина, определяющая класс, имеет доступ только к одному оракулу для одного языка. В этом контексте, не определяется, если класс сложности не имеет полных задач относительно доступных редукций.) Полагается, что NP ⊆ PNP, но вопрос о том, равны ли NPNP, PNP, NP и P, в лучшем случае, остается открытым. Считается, что они различны, и это приводит к определению полиномиальной иерархии. Оракульные машины полезны для исследования взаимосвязи между классами сложности P и NP, рассматривая взаимосвязь между PA и NPA для оракула A. В частности, было показано, что существуют языки A и B, такие, что PA=NPA и PB≠NPB. Тот факт, что вопрос P = NP релятивизируется в обе стороны, рассматривается как свидетельство того, что ответить на этот вопрос сложно, поскольку метод доказательства, который релятивизируется (т.е. не зависит от добавления оракула), не решит вопрос P = NP. Большинство методов доказательства релятивизируются. Можно рассмотреть случай, когда оракул выбирается случайным образом из всех возможных оракулов (бесконечного множества). В этом случае было показано, что с вероятностью 1, PA≠NPA. Когда вопрос верен почти для всех оракулов, он считается верным для случайного оракула. Этот выбор терминологии оправдан тем фактом, что случайные оракулы поддерживают утверждение с вероятностью 0 или 1. (Это следует из закона Колмогорова о нуле и единице.) Это лишь слабое свидетельство того, что P≠NP, поскольку утверждение может быть истинным для случайного оракула, но ложным для обычных машин Тьюринга; например, IPA≠PSPACEA для случайного оракула A, но IP = PSPACE.

Пророчества и проблемы с торможением

Машина с оракулом для задачи останова может определить, остановится ли конкретная машина Тьюринга на конкретном входе, но она не может определить, в общем случае, остановится ли машины, эквивалентные ей самой. Это порождает иерархию машин, каждая из которых обладает более мощным оракулом и ещё более сложной задачей об остановке. Эта иерархия машин может быть использована для определения арифметической иерархии.

Применение в криптографии

В криптографии оракулы используются для обоснования безопасности криптографических протоколов, в которых применяется хеш-функция. Доказывается восстановление безопасности протокола в предположении, что вместо хеш-функции на каждый запрос отвечает случайный оракул, выдавая случайные, но согласованные ответы; считается, что оракул доступен всем участникам, включая атакующего, как и хеш-функция. Такое доказательство показывает, что если атакующему не удается решить сложную задачу, лежащую в основе восстановления безопасности, ему необходимо использовать какое-либо специфическое свойство хеш-функции для взлома протокола; он не может рассматривать хеш-функцию как «черный ящик» (то есть как случайный оракул).