- Сведение по Куку
-
В теории сложности вычислений сведение задачи к по Куку — это полиномиальный по времени алгоритм (другими словами, машина Тьюринга с полиномиальным временем работы), решающий задачу при условии, что функция, находящая решение задачи , ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.
Если такой алгоритм существует, говорят, что сводима по Куку к и пишут
Неформально в таком случае говорят, что «как минимум также сложна» как .
Если задача сводится по Куку к задаче , то решение задачи может быть использовано для решения задачи следующим образом: при запросе алгоритма, вычисляющего , к оракулу используется соответствующее решение . Так как машина Тьюринга может делать запросы к оракулу большое количество раз, итоговый алгоритм решения задачи может потребовать асимптотически больше времени, чем алгоритм, решающий задачу .
История
Первое формальное определение сводимости было предложено Аланом Тьюрингом в 1939 г.
Смотри также
Ссылки
Категории:- Теория сложности вычислений
- Классы сложности
- Сведения
Wikimedia Foundation. 2010.