https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Hardprob%2FShortest_Computation
Hardprob/Shortest Computation - История изменений
2026-04-19T12:26:16Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=Hardprob/Shortest_Computation&diff=23774&oldid=prev
StasFomin: Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Недетерминированная машина Тьюринга <em>M</em>, двоичн…»
2023-04-14T00:09:28Z
<p>Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Недетерминированная машина Тьюринга <em>M</em>, двоичн…»</p>
<p><b>Новая страница</b></p><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --><br />
* Недетерминированная машина Тьюринга <em>M</em>, двоичная входная строка <em>x</em>.<br />
* Найти недерминированную строку-догадку <em>c</em>, произведенную машиной <em>M</em> на входе <em>x</em>.<br />
* Минимизировать длину кратчайшей из этих строк,т.е. <m>\min(\vert c\vert,\vert x\vert) → \min</m>.<br />
<br />
----<br />
{{hard-problem-on-lab17|{{PAGENAME}}}}<br />
<!-- * {{has-testdata-and-visualization}} --><br />
<!-- * {{has-pyomo-model}} --><br />
<!-- * {{has-npc-reduction}} --><br />
<!-- * {{add-random-fuzzing-tests}} --><br />
----<br />
<small><br />
{{ViggoCode|node245}}<br />
<!-- {{GDCode|}} --><br />
<!-- * [ Задача в википедии] --><br />
</small><br />
<!-- end --><br />
<br />
[[Категория:ClassicHardProblems]]</div>
StasFomin