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

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

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

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

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

История

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

См. также

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.