WikiSort.ru - Не сортированное

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

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

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

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

Сложностный класс задач решаемых алгоритмом из класса 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
• https://www.hse.ru/data/2013/05/05/1299516543/11-сс-oracles-notes.pdf

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

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