Сведение (теория сложности вычислений): различия между версиями

В [[Теория сложности вычислений|теории сложности вычислений]] '''сведе́ние''' — преобразование одной проблемы к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры проблемы <math>P_1</math> в экземпляры проблемы <math>P_2</math>, которые имеют тот же ответ (да/нет), то говорят, что '''<math>P_1</math> сводится к <math>P_2</math>'''. Таким образом, '''сводимость''' - это отношение между двумя проблемами. С помощью такой связи могут быть доказаны [[Вычислимая функция|вычислимость]] проблемы или ее принадлежность тому или иному [[Класс сложности|классу сложности]].