Вычисления с оракулом
Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен «угадать» решение
Машина Тьюринга с оракулом
Машина Тьюринга взаимодействует с оракулом путём записи на свою ленту входных данных для оракула и затем запуском оракула на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
Сложностные классы машин с оракулом
Сложностный класс задач решаемых алгоритмом из класса A с оракулом для задачи класса B обозначают AB. Например, класс задач решаемых за полиномиальное время детерминированной машиной Тьюринга с оракулом для NP задачи обозначают PNP.
См. также
Ссылки
- 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
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |
В статье есть список источников, но не хватает сносок. |