Сведение (теория сложности вычислений)

В теории сложности вычислений сведе́ние — преобразование одной задачи к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры задачи $P_1$ в экземпляры задачи $P_2$, которые имеют тот же ответ (да/нет), то говорят, что $P_1$ сводится к $P_2$. Таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или ее принадлежность тому или иному классу сложности.

Некоторые виды сведений

• Сведение по Куку
• Сведение по Карпу
• Сведение по Левину
• Сведение по Тьюрингу (англ.)

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

Ссылки

• Курс «Введение в структурную теорию сложности»

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1