Машина Оракула

Абстрактная машина, используемая для изучения проблем принятия решений

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

Оракулы

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

• Задача принятия решения представляется в виде множества A натуральных чисел (или строк). Экземпляр задачи — произвольное натуральное число (или строка). Решением экземпляра является «ДА», если число (строка) находится в множестве, и «НЕТ» в противном случае.
• Функциональная задача представлена ​​функцией f от натуральных чисел (или строк) до натуральных чисел (или строк). Примером задачи является вход x для f . Решением является значение f ( x ).

Машина оракула может выполнять все обычные операции машины Тьюринга, а также может запрашивать оракул, чтобы получить решение для любого экземпляра вычислительной задачи для этого оракула. ​​Например, если проблема является проблемой принятия решения для множества A натуральных чисел, машина оракула предоставляет оракулу натуральное число, и оракул отвечает «да» или «нет», указывая , является ли это число элементом A.

Определения

Существует много эквивалентных определений оракульных машин Тьюринга, как обсуждается ниже. Представленное здесь определение взято из van Melkebeek (2003, стр. 43).

Машина-оракул, как и машина Тьюринга, включает в себя:

• рабочая лента : последовательность ячеек без начала и конца, каждая из которых может содержать букву B (для пробела) или символ из алфавита ленты;
• головка чтения/записи , которая располагается на одной ячейке рабочей ленты и может считывать данные с нее, записывать новые данные, а также увеличивать или уменьшать свою позицию на ленте;
• механизм управления , который может находиться в одном из конечного числа состояний и который будет выполнять различные действия (чтение данных, запись данных, перемещение механизма управления и изменение состояний) в зависимости от текущего состояния и считываемых данных.

Помимо этих компонентов, машина оракула также включает в себя:

• лента оракула , которая является полубесконечной лентой, отдельной от рабочей ленты. Алфавит для ленты оракула может отличаться от алфавита для рабочей ленты.
• головка оракула , которая, как и головка чтения/записи, может перемещаться влево или вправо по ленте оракула, считывая и записывая символы;
• два специальных состояния: состояние ASK и состояние RESPONSE.

Время от времени машина оракула может входить в состояние ASK. Когда это происходит, в одном вычислительном шаге выполняются следующие действия:

• содержимое ленты оракула рассматривается как пример вычислительной задачи оракула;
• обращаются к оракулу, и содержимое ленты оракула заменяется решением данного экземпляра проблемы;
• голова оракула перемещается на первую клетку на ленте оракула;
• состояние машины оракула изменяется на RESPONSE.

Таким образом, эффект перехода в состояние ASK заключается в получении за один шаг решения экземпляра проблемы, записанного на ленте оракула.

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

Существует много альтернативных определений, представленных выше. Многие из них специализированы для случая, когда оракул решает проблему принятия решения. В этом случае:

• Некоторые определения, вместо записи ответа на ленту оракула, имеют два специальных состояния ДА и НЕТ в дополнение к состоянию ASK. Когда консультируются с оракулом, следующим состоянием выбирается ДА, если содержимое ленты оракула находится в наборе оракула, и выбирается НЕТ, если содержимое не находится в наборе оракула. ^​​[1]
• Некоторые определения избегают отдельной ленты оракула. ​​Когда вводится состояние оракула, указывается символ ленты. Оракулу запрашивается количество раз, которое этот символ ленты появляется на рабочей ленте. Если это число есть в наборе оракула, следующим состоянием является состояние ДА; если нет, следующим состоянием является состояние НЕТ. ^[2]
• Другое альтернативное определение делает ленту оракула доступной только для чтения и полностью устраняет состояния ASK и RESPONSE. Перед запуском машины функция индикатора набора оракула записывается на ленту оракула с использованием символов 0 и 1. Затем машина может запросить оракула, просканировав нужный квадрат на ленте оракула и прочитав значение, расположенное там. ^[3]

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

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

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

${\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}$

Когда язык L является полным для некоторого класса B, то A ^L =A ^B при условии, что машины в A могут выполнять сокращения, используемые в определении полноты класса B. В частности, поскольку SAT является NP-полным относительно сокращений за полиномиальное время, P ^SAT =P ^NP . Однако, если A = DLOGTIME , то A ^SAT может не равняться A ^NP . (Определение, данное выше, не является полностью стандартным. В некоторых контекстах, таких как доказательство теорем об иерархии времени и пространства , более полезно предположить, что абстрактная машина, определяющая класс, имеет доступ только к одному оракулу для одного языка. В этом контексте не определяется, если класс сложности не имеет никаких полных проблем относительно сокращений, доступных для .) ${\displaystyle A^{B}}$ ${\displaystyle A}$ ${\displaystyle A^{B}}$ ${\displaystyle B}$ ${\displaystyle A}$

Понятно, что NP ⊆ P ^NP , но вопрос о том, равны ли NP ^NP , P ^NP , NP и P , остается в лучшем случае предварительным. Считается, что они различны, и это приводит к определению полиномиальной иерархии .

Машины Oracle полезны для исследования взаимосвязи между классами сложности P и NP , рассматривая взаимосвязь между P ^A и NP ^A для оракула A. В частности, было показано, что существуют языки A и B, такие что P ^A = NP ^A и P ^B ≠ NP ^B . ^[4] Тот факт, что вопрос P = NP релятивизирует оба способа, рассматривается как доказательство того, что ответить на этот вопрос сложно, потому что метод доказательства, который релятивизирует (т. е. не зависит от добавления оракула), не ответит на вопрос P = NP. ^[5] Большинство методов доказательства релятивизируют. ^[6]

Можно рассмотреть случай, когда оракул выбирается случайным образом из всех возможных оракулов (бесконечное множество). В этом случае было показано, что с вероятностью 1 P ^A ≠NP ^A . ^[7] Когда вопрос истинен для почти всех оракулов, говорят, что он истинен для случайного оракула . Такой выбор терминологии оправдан тем фактом, что случайные оракулы поддерживают утверждение с вероятностью только 0 или 1. (Это следует из закона Колмогорова «ноль-один »). Это лишь слабое доказательство того, что P ≠ NP, поскольку утверждение может быть истинным для случайного оракула, но ложным для обычных машин Тьюринга; ^{[ оригинальное исследование? ]} например, IP ^A ≠ PSPACE ^A для случайного оракула A, но IP = PSPACE . ^[8]

Оракулы и проблемы остановки

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

Приложения к криптографии

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

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

• Группа черного ящика
• Редукция Тьюринга
• Интерактивная система доказательств
• Оракул матроида
• Оракул спроса
• Атака оракула с заполнением

Ссылки

Сноски

1. Адачи 1990, стр. 111.
2. Роджерс 1967, стр. 129.
3. Соаре 1987, с. 47; Роджерс 1967, с. 130.
4. Бейкер, Гилл и Соловей 1975, стр. 431.
5. Тревизан 2014, стр. 2.
6. Тревизан 2014, стр. 1.
7. Беннетт и Гилл 1981, стр. 96.
8. Чанг и др. 1994, стр. 29.
9. Бёргер 1989, стр. 141.

Источники

• Адачи, Акео (1990). Основы теории вычислений . Токио: Ohmsha. ISBN 978-4-274-02190-9.
• Бейкер, Теодор; Гилл, Джон; Соловей, Роберт (декабрь 1975 г.). «Relativizations of the P=?NP Question» (PDF) . SIAM Journal on Computing . 4 (4). doi :10.1137/0204037. ISSN  0097-5397. Архивировано (PDF) из оригинала 19 марта 2023 г. . Получено 21 октября 2023 г. .
• Беннетт, Чарльз Х .; Гилл, Джон (февраль 1981 г.). «Относительно случайного оракула A, PA != NPA != co-NPA с вероятностью 1» (PDF) . SIAM Journal on Computing . 10 (1). doi :10.1137/0210008. ISSN  0097-5397. Архивировано (PDF) из оригинала 25 декабря 2022 г.
• Бёргер, Эгон (1989). Вычислимость, сложность, логика . Исследования по логике и основаниям математики. Амстердам: Северная Голландия. ISBN 978-0-444-87406-1.
• Чанг, Ричард; Чор, Бенни ; Голдрайх, Одед ; Хартманис, Юрис ; Хастад, Йохан ; Ранджан, Деш; Рохатги, Панкадж (1 августа 1994 г.). «Гипотеза случайного оракула ложна» (PDF) . Журнал компьютерных и системных наук . 49 (1): 24–39. doi : 10.1016/S0022-0000(05)80084-4 . ISSN  0022-0000.
• Дэвис, Мартин , ред. (1 апреля 1965 г.). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Хьюлетт, Нью-Йорк: Raven Press. ISBN 978-0-911216-01-1. Получено 21 октября 2023 г. .
• Пападимитриу, Христос (30 ноября 1993 г.). Сложность вычислений . Рединг, Массачусетс: Addison-Wesley. ISBN 978-0-201-53082-7.
• Роджерс, Хартли (1 апреля 1967 г.). Теория рекурсивных функций и эффективная вычислимость . Нью-Йорк: McGraw-Hill. OCLC  559483934.
• Сипсер, Майкл (1997). Введение в теорию вычислений . Бостон: PWS Publishing. ISBN 978-0-534-94728-6. OCLC  300459879.
• Soare, Robert I. (1987). Рекурсивно перечислимые множества и степени . Перспективы в математической логике (1-е изд.). Springer Berlin, Heidelberg. doi :10.1007/978-3-662-02460-7_3 (неактивен 8 ноября 2024 г.). ISSN  0172-6641.{{cite book}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
• Тревизан, Лука (16 января 2014 г.). «Заметки к лекции 4» (PDF) . CS254: Computational Complexity. Стэнфордский университет. Архивировано (PDF) из оригинала 1 апреля 2014 г. . Получено 22 октября 2023 г. .
• Тьюринг, Алан (1939). Системы логики на основе ординалов (диссертация доктора философии). Принстонский университет. doi : 10.1112/plms/s2-45.1.161. hdl : 21.11116/0000-0001-91CE-3 . ProQuest  301792588. Архивировано из оригинала 13 марта 2020 г.
• ван Мелкебек, Дитер (29 июня 2003 г.). Случайность и полнота в вычислительной сложности . Конспект лекций по информатике. Том 1950. Springer Berlin Heidelberg. doi :10.1007/3-540-44545-5. ISBN 978-3-540-44545-6. ISSN  1611-3349. OCLC  48909425. S2CID  27442913.