https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%A1%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C_%D0%BF%D0%BE_%D0%9A%D0%B0%D1%80%D0%BF%D1%83 2026-04-30T22:35:55Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C_%D0%BF%D0%BE_%D0%9A%D0%B0%D1%80%D0%BF%D1%83&diff=1287&oldid=prev 2008-08-04T09:55:53Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Задача разрешения ''P&lt;sub&gt;1&lt;/sub&gt;'' '''полиномиально сводится''' (по Карпу) к задаче разрешения ''P&lt;sub&gt;2&lt;/sub&gt;'', если существует полиномиально вычислимая функция ''f'', перерабатывающая<br /> массивы входных данных ''I&lt;sub&gt;1&lt;/sub&gt;'' для задачи ''P&lt;sub&gt;1&lt;/sub&gt;'' в массивы входных<br /> данных &lt;amsmath&gt;I_2 \equiv f(I)&lt;/amsmath&gt; для задачи ''P&lt;sub&gt;2&lt;/sub&gt;'' таким образом, что для любого ''I'' ответ<br /> в задаче ''P&lt;sub&gt;1&lt;/sub&gt;'' совпадает с ответом задачи ''P&lt;sub&gt;2&lt;/sub&gt;'' для входных<br /> данных ''f(I)''.<br /> <br /> [[Category:Теория сложности]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop