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

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

Если такой алгоритм существует, говорят, что $R_1$ сводима по Куку к $R_2$ и пишут

$R_1{\le }_C{R}_2.$

Неформально в таком случае говорят, что $R_2$ «как минимум так же сложна» как $R_1$.

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

История

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

См. также

• Сведение

Ссылки

• Курс «Введение в структурную теорию сложности»
• Шаблон:PlanetMath