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

Сводимость по Карпу — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Category:Теория сложности+репликация.)
(нет различий)

Версия 16:48, 7 декабря 2005

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


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

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