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