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

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Задача разрешения ''P<sub>1</sub>'' '''полиномиально сводится''' (по Карпу) к задаче разрешения ''P<sub>2</sub>'', если существует полиномиально вычислимая функция ''f'', перерабатывающая
+
#REDIRECT [[discopal:{{PAGENAME}}]]
массивы входных данных ''I<sub>1</sub>'' для задачи ''P<sub>1</sub>'' в массивы входных
+
данных <amsmath>I_2 \equiv f(I)</amsmath> для задачи ''P<sub>2</sub>'' таким образом, что для любого ''I'' ответ
+
в задаче ''P<sub>1</sub>'' совпадает с ответом задачи ''P<sub>2</sub>'' для входных
+
данных ''f(I)''.
+
 
+
[[Category:Теория сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:31, 13 июня 2011

  1. REDIRECT discopal:Сводимость по Карпу