https://lib.custis.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-06-22T01:04:11Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://lib.custis.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=27244&oldid=prev
StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»
2011-06-13T17:31:34Z
<p>Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 17:31, 13 июня 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Задача разрешения ''P<sub>1</sub>'' '''полиномиально сводится''' (по Карпу) к задаче разрешения ''P<sub>2</sub>'', если существует полиномиально вычислимая функция ''f'', перерабатывающая</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">#REDIRECT </ins>[[<ins class="diffchange diffchange-inline">discopal</ins>:{{<ins class="diffchange diffchange-inline">PAGENAME</ins>}}<ins class="diffchange diffchange-inline">]]</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">массивы входных данных ''I<sub>1</sub>'' для задачи ''P<sub>1</sub>'' в массивы входных</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">данных <amsmath>I_2 \equiv f(I)</amsmath> для задачи ''P<sub>2</sub>'' таким образом, что для любого ''I'' ответ</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">в задаче ''P<sub>1</sub>'' совпадает с ответом задачи ''P<sub>2</sub>'' для входных</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">данных ''f(I)''.</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[<del class="diffchange diffchange-inline">Category</del>:<del class="diffchange diffchange-inline">Теория сложности]]</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>{{<del class="diffchange diffchange-inline">replicate-from-custiswiki-to-lib</del>}}</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
</table>
StasFomin
https://lib.custis.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=9837&oldid=prev
WikiSysop: 1 версия
2008-08-04T09:55:53Z
<p>1 версия</p>
<table class='diff diff-contentalign-left'>
<tr style='vertical-align: top;' lang='ru'>
<td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 09:55, 4 августа 2008</td>
</tr><tr><td colspan='2' style='text-align: center;' class='diff-multi' lang='ru'>(не показана 1 промежуточная версия 1 участника)</td></tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div>
</td></tr></table>
WikiSysop
https://lib.custis.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=2925&oldid=prev
BenderBot: реплицировано из внутренней CustisWiki
2005-12-08T04:42:18Z
<p>реплицировано из внутренней CustisWiki</p>
<p><b>Новая страница</b></p><div>Задача разрешения ''P<sub>1</sub>'' '''полиномиально сводится''' (по Карпу) к задаче разрешения ''P<sub>2</sub>'', если существует полиномиально вычислимая функция ''f'', перерабатывающая<br />
массивы входных данных ''I<sub>1</sub>'' для задачи ''P<sub>1</sub>'' в массивы входных<br />
данных <amsmath>I_2 \equiv f(I)</amsmath> для задачи ''P<sub>2</sub>'' таким образом, что для любого ''I'' ответ<br />
в задаче ''P<sub>1</sub>'' совпадает с ответом задачи ''P<sub>2</sub>'' для входных<br />
данных ''f(I)''.<br />
<br />
[[Category:Теория сложности]]<br />
{{replicate-from-custiswiki-to-lib}}</div>
BenderBot
https://lib.custis.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=9836&oldid=prev
StasFomin: Category:Теория сложности+репликация.
2005-12-07T13:48:03Z
<p><a href="/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8" title="Категория:Теория сложности">Category:Теория сложности</a>+репликация.</p>
<table class='diff diff-contentalign-left'>
<tr style='vertical-align: top;' lang='ru'>
<td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 13:48, 7 декабря 2005</td>
</tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div>
</td></tr></table>
StasFomin