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