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

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

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

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

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

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

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

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

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