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

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

---

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