Сведе́ние в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи в экземпляры задачи , которые имеют тот же ответ («да» или «нет»), говорят, что сводится к , таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или её принадлежность тому или иному классу сложности.
Некоторые виды сведений: сведение по Куку, сведение по Карпу, сведение по Левину, сведение по Тьюрингу . Сведение по Тьюрингу — наиболее общая форма сведения: некоторый алгоритм (вычислимый на машине Тьюринга) может быть вызван любое количество раз, при этом каждый вызов будет считаться за один шаг алгоритма; для формального определения сводимости по Тьюрингу используется понятие тьюринг-машины с оракулом.
Энциклопедичный YouTube
-
1/3Просмотров:1 0211 38610 767
-
003. Класс NP. Сведение задач друг к другу - Н.К.Верещагин
-
002. Теорема об иерархии. Сведение задач друг к другу - Н.К.Верещагин
-
001. Вычислительные модели. Машины Тьюринга и арифметические алгоритмы - Н.К.Верещагин
Субтитры
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.
Ссылки
Обычно почти сразу, изредка в течении часа.