|
 |
Персональные инструменты
Просмотры |
|
Персональные инструменты |
|
||
|
|
Сводимость по Карпу — различия между версиямиМатериал из CustisWiki
Версия 16:48, 7 декабря 2005Задача разрешения P1 полиномиально сводится (по Карпу) к задаче разрешения P2, если существует полиномиально вычислимая функция f, перерабатывающая массивы входных данных I1 для задачи P1 в массивы входных данных для задачи P2 таким образом, что для любого I ответ в задаче P1 совпадает с ответом задачи P2 для входных данных f(I).
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Сводимость по Карпу» |
 |
||||
 |
||||||
 |
