Вычисления с оракулом

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Машина Тьюринга с оракулом[править | править вики-текст]

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

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

Сложностный класс задач решаемых алгоритмом из класса A с оракулом для задачи класса B обозначают AB. Например, класс задач решаемых за полиномиальное время детерминированной машиной Тьюринга с оракулом для NP задачи обозначают PNP.

См. также[править | править вики-текст]

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