Сведение по Куку
В теории сложности вычислений сведение задачи R 1 {displaystyle R_{1}} к R 2 {displaystyle R_{2}} по Куку — это полиномиальный по времени алгоритм (другими словами, машина Тьюринга с полиномиальным временем работы), решающий задачу R 1 {displaystyle R_{1}} при условии, что функция, находящая решение задачи R 2 {displaystyle R_{2}} , ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.
Если такой алгоритм существует, говорят, что R 1 {displaystyle R_{1}} сводима по Куку к R 2 {displaystyle R_{2}} и пишут
R 1 ≤ C R 2 . {displaystyle R_{1}leq _{C}R_{2}.}Неформально в таком случае говорят, что R 2 {displaystyle R_{2}} «как минимум так же сложна» как R 1 {displaystyle R_{1}} .
Если задача R 1 {displaystyle R_{1}} сводится по Куку к задаче R 2 {displaystyle R_{2}} , то решение задачи R 2 {displaystyle R_{2}} может быть использовано для решения задачи R 1 {displaystyle R_{1}} следующим образом: при запросе алгоритма, вычисляющего R 1 {displaystyle R_{1}} , к оракулу используется соответствующее решение R 2 {displaystyle R_{2}} . Так как машина Тьюринга может делать запросы к оракулу большое количество раз, итоговый алгоритм решения задачи R 1 {displaystyle R_{1}} может потребовать асимптотически больше времени, чем алгоритм, решающий задачу R 2 {displaystyle R_{2}} .
История
Первое формальное определение сводимости было предложено Аланом Тьюрингом в 1939 г.