Сводимость по Карпу

Материал из свободной русской энциклопедии «Традиция». Вы можете дополнить или исправить его.
Перейти к навигации Перейти к поиску

Задача разрешения P1 полиномиально сводится (по Карпу) к задаче разрешения P2, если существует полиномиально вычислимая функция f, перерабатывающая массивы входных данных I1 для задачи P1 в массивы входных данных I2f(I)I_2 \equiv f(I) для задачи P2 таким образом, что для любого I ответ в задаче P1 совпадает с ответом задачи P2 для входных данных f(I).


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.