машина Oracle

Информацию о компьютерном оборудовании, продаваемом корпорацией Oracle, см. в разделе «Аппаратное обеспечение» корпорации Oracle .

Системы черного ящика
Система
Черный ящик , машина Oracle
Методы и техники
Тестирование «черного ящика» , «черный ящик»
Связанные методы
Упреждение , Обфускация , Распознавание образов , Белый ящик , Тестирование белого ящика , Тестирование серого ящика , Идентификация системы
Основы
Априорная информация , Системы управления , Открытые системы , Исследование операций , Термодинамические системы

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

Оракулы

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

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

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

Определения

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

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

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

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

• лента оракула , представляющая собой полубесконечную ленту, отдельную от рабочей ленты. Алфавит ленты оракула может отличаться от алфавита рабочей ленты.
• головка оракула , которая, как и головка чтения/записи, может перемещаться влево или вправо по ленте оракула, читая и записывая символы;
• два особых состояния: состояние СПРОС и состояние ОТВЕТ.

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

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

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

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

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

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

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

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

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

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

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

Понятно, что NP ⊆ P ^{НАПРИМЕР} , но вопрос о том, является ли NP ^{НАПРИМЕР} , П ^{НАПРИМЕР} , NP и P равны, остается в лучшем случае приблизительным. Считается, что они разные, и это приводит к определению полиномиальной иерархии .

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

Можно рассмотреть случай, когда оракул выбирается случайным образом среди всех возможных оракулов (бесконечное множество). При этом было показано, что с вероятностью 1 P ^А ≠NP ^А . Когда вопрос верен почти для всех оракулов, говорят, что он истинен для случайного оракула . Такой выбор терминологии оправдан тем фактом, что случайные оракулы поддерживают утверждение только с вероятностью 0 или 1. (Это следует из закона нуля–единицы Колмогорова .) Это лишь слабое доказательство того, что P≠NP, поскольку утверждение может быть истинным для случайного оракула, но ложным для обычных машин Тьюринга; например, ИП ^А ≠PSPACE ^А для случайного оракула A, но IP = PSPACE .

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

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

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

Основная статья: Случайный оракул

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

См. также

• Группа «черный ящик»
• Сокращение Тьюринга
• Интерактивная система доказательств
• Матроид-оракул
• Спрос оракула
• Заполнение атаки оракула

Ссылки

Источники

• Адачи, Акео (1990). Основы теории вычислений . Токио: Омша. ISBN  978-4-274-02190-9 .
• Бейкер, Теодор; Гилл, Джон; Соловей, Роберт (декабрь 1975 г.). «Релятивизация вопроса P =?NP» (PDF) . SIAM Journal по вычислительной технике . 4 (4). дои : 10.1137/0204037 . ISSN   0097-5397 . Архивировано (PDF) из оригинала 19 марта 2023 года . Проверено 21 октября 2023 г.
• Беннетт, Чарльз Х .; Гилл, Джон (февраль 1981 г.). «Относительно случайного оракула A, P ^А != НАПРИМЕР ^А != со-NP ^А с вероятностью 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. дои : 10.1016/S0022-0000(05)80084-4 . ISSN   0022-0000 .
• Дэвис, Мартин , изд. (1 апреля 1965 г.). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Хьюлетт, Нью-Йорк: Raven Press. ISBN  978-0-911216-01-1 . Проверено 21 октября 2023 г.
• Пападимитриу, Христос (30 ноября 1993 г.). Вычислительная сложность . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN  978-0-201-53082-7 .
• Роджерс, Хартли (1 апреля 1967 г.). Теория рекурсивных функций и эффективная вычислимость . Нью-Йорк: МакГроу-Хилл. OCLC   559483934 .
• Сипсер, Майкл (1997). Введение в теорию вычислений . Бостон: Издательство PWS. ISBN  978-0-534-94728-6 . OCLC   300459879 .
• Соаре, Роберт И. (1987). Рекурсивно перечислимые множества и степени . Перспективы математической логики (1-е изд.). Шпрингер Берлин, Гейдельберг. дои : 10.1007/978-3-662-02460-7_3 . ISSN   0172-6641 .
• Тревизан, Лука (16 января 2014 г.). «Примечания к лекции 4» (PDF) . CS254: Вычислительная сложность. Стэнфордский университет. Архивировано (PDF) из оригинала 1 апреля 2014 г. Проверено 22 октября 2023 г.
• Тьюринг, Алан (1939). Системы логики на основе ординалов (кандидатская диссертация). Принстонский университет. дои : 10.1112/plms/s2-45.1.161 . hdl : 21.11116/0000-0001-91CE-3 . ПроКвест   301792588 . Архивировано из оригинала 13 марта 2020 года.
• ван Мелкебек, Дитер (29 июня 2003 г.). Случайность и полнота в вычислительной сложности . Конспекты лекций по информатике. Том. 1950. Шпрингер Берлин Гейдельберг. дои : 10.1007/3-540-44545-5 . ISBN  978-3-540-44545-6 . ISSN   1611-3349 . OCLC   48909425 . S2CID   27442913 .