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

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

---

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Сводимость по Карпу»