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

Ссылки сюда (1) →

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.