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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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

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