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