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

10.06.2021

Сведение в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи P 1 {displaystyle P_{1}} в экземпляры задачи P 2 {displaystyle P_{2}} , которые имеют тот же ответ («да» или «нет»), говорят, что P 1 {displaystyle P_{1}} сводится к P 2 {displaystyle P_{2}} , таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или её принадлежность тому или иному классу сложности.

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