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

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

Машина Тьюринга с оракулом

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

Сложностные классы машин с оракулом

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

См. также

• Теория сложности вычислений

Ссылки

• http://www.isical.ac.in/~arijit/courses/spring2010/slides/complexitylec13.pdf
• http://www.people.cs.uchicago.edu/~soare/History/turing.pdf
• [1]
• https://www.hse.ru/data/2013/05/05/1299516543/11-сс-oracles-notes.pdf