Машина Oracle

Системы черного ящика
Система
Черный ящик  · машина Oracle
Методы и приемы
Тестирование черного ящика  · Blackboxing
Связанные методы
Прямая связь  · Обфускация  · Распознавание образов  · Белый ящик  · Тестирование белого ящика  · Идентификация системы
Основы
Априорная информация  · Системы управления  · Открытые системы  · Исследование операций  · Термодинамические системы
v т е

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

Оракулы [ править ]

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

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

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

Определения [ править ]

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

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

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

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

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

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

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

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

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

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

• В некоторых определениях вместо записи ответа на ленту оракула есть два специальных состояния YES и NO в дополнение к состоянию ASK. При обращении к оракулу следующее состояние выбирается как ДА, если содержимое ленты оракула находится в наборе оракула, и выбирается как НЕТ, если содержимое не находится в наборе оракула (Adachi 1990: 111).
• Некоторые определения избегают отдельной ленты оракула. При входе в состояние оракула указывается символ ленты. Оракулу задают вопрос, сколько раз этот символ ленты появляется на рабочей ленте. Если это число находится в наборе оракула, следующим состоянием будет состояние ДА; если это не так, следующим состоянием будет состояние НЕТ (Rogers 1967: 129).
• Другое альтернативное определение делает ленту oracle доступной только для чтения и полностью исключает состояния ASK и RESPONSE. Перед запуском машины индикаторная функция набора оракула записывается на ленту оракула с использованием символов 0 и 1. Затем машина может запросить оракула, отсканировав правильный квадрат на ленте оракула и прочитав значение, расположенное там. (Соар 1987: 47, Роджерс 1967: 130).

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

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

Сложность класс из задач принятия решений разрешимых алгоритма в классе А с оракулом для языка L называется ^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 может не равняться ^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 (Бейкер, Гилл и Соловей, 1975). Тот факт, что вопрос P = NP релятивизирует оба пути, принимается как свидетельство того, что ответить на этот вопрос сложно, потому что метод доказательства, который релятивизирует (т.е. не влияет на добавление оракула), не ответит на вопрос P = NP. Большинство методов доказательства релятивизируют.

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

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

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

Приложения к криптографии [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

• Акео Адачи, Основы теории вычислений , Омша, 1990.
• Т. П. Бейкер, Дж. Гилл, Р. Соловей . Релятивизации P =? Н.П. Вопрос . SIAM Journal on Computing , 4 (4): 431-442 (1975).
• CH Беннетт, Дж. Гилл. Относительно случайного оракула A, P ^A  ! = NP ^A  ! = Co-NP ^A с вероятностью 1 . SIAM Journal on Computing, 10 (1): 96-113 (1981).
• Эгон Бёргер. «Вычислимость, сложность, логика». Северная Голландия, 1989 г.
• Ричард Чанг, Бенни Чор, Одед Голдрайх, Юрис Хартманис, Йохан Хастад, Деш Ранджан, Панкадж Рохатги. Гипотеза случайного оракула неверна. Журнал компьютерных и системных наук , том 49, выпуск 1, стр. 24–39. Август 1994. ISSN  0022-0000 . http://citeseer.ist.psu.edu/282397.html
• Мартин Дэвис , редактор: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions , Raven Press, New York, 1965. Статья Тьюринга находится в этом томе. Среди статей - Гедель, Черч, Россер, Клини и Пост.
• C. Papadimitriou. Вычислительная сложность . Эддисон-Уэсли, 1994. Раздел 14.3: Оракулы, стр. 339–343.
• Хартли Роджерс младший, Теория рекурсивных функций и эффективная вычислимость , McGraw-Hill, 1967.
• Майкл Сипсер . Введение в теорию вычислений . PWS Publishing, 1997. ISBN 0-534-94728-X . Раздел 9.2: Релятивизация, стр. 318–321. 
• Роберт И. Соаре, Рекурсивно перечислимые множества и степени , Перспективы математической логики, Springer, 1987.
• Алан Тьюринг, Системы логики на основе ординалов , Proc. Лондонская математика. соц., 45 , 1939
• Дитер ван Мелкебек, Случайность и полнота в вычислительной сложности , Конспект лекций по информатике 1950, Springer, 2000.