Войти
| Системы черного ящика | |
|---|---|
 | |
| Система | |
| Черный ящик ·Машина Oracle | |
| Методы и методы | |
| Тестирование черного ящика ·Черный ящик | |
| Связанные методы | |
| Прямая связь ·Обфускация ·Распознавание образов ·Белый ящик ·Тестирование белого ящика ·Идентификация системы | |
| Основы | |
| Априорная информация ·Системы управления ·Открытые системы ·Исследование операций ·Термодинамические системы | |
|
В теории сложности и вычислимости Согласно теории, машина-оракул - это абстрактная машина, используемая для изучения проблем принятия решений. Его можно представить себе как машину Тьюринга с черным ящиком, называемую оракулом, которая способна решать определенные проблемы принятия решений за одну операцию. Проблема может быть любой класса сложности. Можно использовать даже неразрешимые проблемы, такие как проблема остановки.
Машину оракула можно представить как машину Тьюринга, соединенную с оракулом . В этом контексте оракул - это объект, способный решить некоторую проблему, которая, например, может быть проблемой решения или функциональной проблемой. Проблема не обязательно должна быть вычислимой; Оракул не считается машиной Тьюринга или компьютерной программой. Оракул - это просто «черный ящик », который может дать решение для любого случая данной вычислительной проблемы:
Машина-оракул может выполнять все обычные операции машины Тьюринга, а также может запрашивать у оракула решение любого экземпляра вычислительной проблемы для этого оракула. Например, если проблема является проблемой решения для набора натуральных чисел A, машина оракула предоставляет оракулу натуральное число, и оракул отвечает «да» или «нет», указывая, является ли это число элементом A..
Существует множество эквивалентных определений оракульных машин Тьюринга, как обсуждается ниже. Тот, что представлен здесь, принадлежит ван Мелкебеку (2000: 43).
Машина оракула, как и машина Тьюринга, включает:
В дополнение к этим компонентам машина оракула также включает:
Время от времени машина-оракул может переходить в состояние ASK. Когда это происходит, следующие действия выполняются за один вычислительный шаг:
Эффект перехода в состояние ASK, таким образом, заключается в получении за один шаг решения проблемы, записанной на ленте оракула.
Есть много альтернативных определений, приведенных выше. Многие из них предназначены для случая, когда оракул решает проблему принятия решения. В этом случае:
Эти определения эквивалентны с точки зрения вычислимости по Тьюрингу: функция вычислима с помощью оракула из данного оракула согласно всем этим определениям, если он вычислим с помощью оракула при любом из них. Однако определения не эквивалентны с точки зрения вычислительной сложности. Как правило, требуется определение, подобное тому, которое сделал ван Мелкебек, используя ленту оракула, которая может иметь собственный алфавит.
классом задач принятия решений, решаемых алгоритмом в классе A с оракулом для языка L, является называется A. Например, P - это класс задач, решаемых за полиномиальное время с помощью детерминированной машины Тьюринга с оракулом для задачи логической выполнимости. Обозначение A может быть расширено до набора языков B (или класса сложности B), используя следующее определение:
Когда язык L завершен для некоторого класса B, тогда A = A при условии, что машины в A могут выполнять сокращения, используемые в определении полноты класса B. В частности, поскольку SAT является NP-полным в отношении полиномиального сокращения времени, P = P. Однако, если A = DLOGTIME, то A может не равняться A. (Обратите внимание, что определение 
Понятно, что NP ⊆ P, но вопрос о том, NP, P, NP и P равны в лучшем случае. Считается, что они разные, и это приводит к определению полиномиальной иерархии.
Машины Oracle полезны для исследования взаимосвязи между классами сложности P и NP, учитывая взаимосвязь между P и NP для оракула A. В частности, было показано, что существуют языки A и B такие, что P = NP и P ≠ NP (Бейкер, Гилл и Соловей, 1975). Тот факт, что вопрос P = NP релятивизирует оба пути, рассматривается как доказательство того, что ответить на этот вопрос сложно, потому что метод доказательства, который релятивизирует (т.е. не влияет на добавление оракула), не ответит на вопрос P = NP. Большинство методов доказательства релятивизируют.
Можно рассмотреть случай, когда оракул выбирается случайным образом из всех возможных оракулов (бесконечное множество). В этом случае было показано, что с вероятностью 1 P ≠ NP (Bennett and Gill 1981). Когда вопрос верен почти для всех оракулов, он считается верным для случайного оракула. Такой выбор терминологии оправдан тем фактом, что случайные оракулы поддерживают утверждение только с вероятностью 0 или 1. (Это следует из закона нуля или единицы Колмогорова.) Это лишь слабое свидетельство того, что P ≠ NP, поскольку утверждение может быть истинным для случайного оракула, но ложным для обычных машин Тьюринга; например, IP ≠ PSPACE для случайного оракула A, но IP = PSPACE (Chang et al., 1994).
Машина с оракулом для проблемы остановки может определить, остановятся ли определенные машины Тьюринга при определенных входных данных, но они не могут определить, в целом остановятся ли машины, эквивалентные самим себе. Это создает иерархию машин, каждая из которых имеет более мощный останавливающий оракул и еще более сложную проблему остановки. Эту иерархию машин можно использовать для определения арифметической иерархии (Börger 1989).
В криптографии оракулы используются для создания аргументов в пользу безопасности криптографических протоколов, где используется хэш-функция . снижение безопасности для протокола дается в случае, когда вместо хэш-функции случайный оракул отвечает на каждый запрос случайным образом, но последовательно; предполагается, что оракул доступен всем сторонам, включая злоумышленника, как и хэш-функция. Такое доказательство показывает, что если злоумышленник не решит сложную проблему, лежащую в основе снижения безопасности, он должен использовать какое-то интересное свойство хэш-функции, чтобы нарушить протокол; они не могут рассматривать хеш-функцию как черный ящик (т.е. как случайный оракул).
