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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Некоторые виды сведений[править | править вики-текст]

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

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

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