https://discopal.ispras.ru/index.php?action=history&feed=atom&title=PSPACE 2026-04-26T20:12:20Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=PSPACE&diff=812&oldid=prev 2008-08-04T09:55:49Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Класс задач, разрешимых на [[Машина Тьюринга|машине Тьюринга]], причем существует алгоритм ([[машина Тьюринга]]), использующий память не более чем полиномиального размера от длины входа.<br /> <br /> Более формально, через определение класса [[DSPACE]]:<br /> <br /> &lt;amsmath&gt;{\cal PSPACE} \equiv \cup_{c&gt;0} {\cal DSPACE}(n^c)&lt;/amsmath&gt;<br /> <br /> [[Category:Классы сложности]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop