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

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

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

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

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

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

История

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

См. также

• Сведение

Ссылки

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