Сведение по Куку

В теории сложности вычислений сведение задачи ${\displaystyle R_{1}}$ к ${\displaystyle R_{2}}$ по Куку — это полиномиальный по времени алгоритм (другими словами, машина Тьюринга с полиномиальным временем работы), решающий задачу ${\displaystyle R_{1}}$ при условии, что функция, находящая решение задачи ${\displaystyle R_{2}}$, ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.

Если такой алгоритм существует, говорят, что ${\displaystyle R_{1}}$ сводима по Куку к ${\displaystyle R_{2}}$ и пишут

${\displaystyle R_{1}\leq _{C}R_{2}.}$

Неформально в таком случае говорят, что ${\displaystyle R_{2}}$ «как минимум так же сложна» как ${\displaystyle R_{1}}$.

Если задача ${\displaystyle R_{1}}$ сводится по Куку к задаче ${\displaystyle R_{2}}$, то решение задачи ${\displaystyle R_{2}}$ может быть использовано для решения задачи ${\displaystyle R_{1}}$ следующим образом: при запросе алгоритма, вычисляющего ${\displaystyle R_{1}}$, к оракулу используется соответствующее решение ${\displaystyle R_{2}}$. Так как машина Тьюринга может делать запросы к оракулу большое количество раз, итоговый алгоритм решения задачи ${\displaystyle R_{1}}$ может потребовать асимптотически больше времени, чем алгоритм, решающий задачу ${\displaystyle R_{2}}$.

История

Первое формальное определение сводимости было предложено Аланом Тьюрингом в 1939 г.

См. также

• Сведение

Ссылки

• Курс «Введение в структурную теорию сложности»
• Cook Reduction (Сведение по Куку) (англ.) на сайте PlanetMath.

Эта страница в последний раз была отредактирована 21 июня 2018 в 17:04.