Сводимость по Карпу
Перейти к навигации
Перейти к поиску
Задача разрешения P1 полиномиально сводится (по Карпу) к задаче разрешения P2, если существует полиномиально вычислимая функция f, перерабатывающая
массивы входных данных I1 для задачи P1 в массивы входных
данных
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.