|
|
| (не показана 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}} | + | |
