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

16.12.2021

В теории сложности вычислений сведение задачи 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 г.


Имя:*
E-Mail:
Комментарий: