Персональные инструменты
 

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

Материал из CustisWiki

Версия от 07:42, 8 декабря 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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


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

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