Сводимость по Карпу — различия между версиями

Версия 12:55, 4 августа 2008

Задача разрешения P₁ полиномиально сводится (по Карпу) к задаче разрешения P₂, если существует полиномиально вычислимая функция f, перерабатывающая массивы входных данных I₁ для задачи P₁ в массивы входных данных для задачи P₂ таким образом, что для любого I ответ в задаче P₁ совпадает с ответом задачи P₂ для входных данных f(I).