Машина-оракул
-
Определение и использование оракулов
- Оракул — это машина, которая может отвечать на вопросы о состоянии других машин.
- Оракулы используются для решения задач, которые не могут быть решены обычными машинами Тьюринга.
-
Примеры оракулов
- Машина Тьюринга с оракулом для задачи выполнимости булевых формул (PSAT) решает задачи за полиномиальное время.
- Машина Тьюринга с оракулом для задачи остановки может определить, останавливается ли другая машина.
-
Классы сложности оракулов
- Класс сложности AL определяется как задачи, решаемые с помощью оракула для языка L.
- Обозначение AB может быть расширено для набора языков B, если язык L завершен для класса B.
-
Связь между P и NP
- Оракулы помогают исследовать взаимосвязь между классами P и NP, например, PA и NPA.
- Вопрос P = NP релятивизируется в обоих направлениях, что указывает на сложность ответа на него.
-
Применение оракулов в криптографии
- Оракулы используются для доказательства безопасности криптографических протоколов.
- Доказательство безопасности основано на том, что злоумышленник не может использовать хэш-функцию как случайный оракул.
-
Иерархия машин с оракулами
- Машины с более мощными оракулами для остановки создают иерархию, которая может использоваться для определения арифметической иерархии.
-
Рекомендации
- Статья содержит сноски и источники, а также информацию о форматировании и стилизации.