Уменьшение пространства журнала

В теории сложности вычислений сокращение логарифмического пространства — это сокращение , вычислимое детерминированной машиной Тьюринга с использованием логарифмического пространства . постоянное количество указателей Концептуально это означает, что он может хранить на входе , а также логарифмическое количество целых чисел фиксированного размера . Вполне возможно, что у такой машины может не хватить места для записи собственных результатов, поэтому единственным требованием является то, чтобы любой бит вывода был вычислим в пространстве журнала. Формально это сокращение выполняется через преобразователь логарифмического пространства .

Такая машина имеет полиномиальное количество конфигураций, поэтому сокращение пространства журнала также является сокращением полиномиального времени . Однако сокращение логарифмического пространства, вероятно, слабее, чем сокращение полиномиального времени; в то время как любой непустой, неполный язык в P полиномиально сводим к любому другому непустому, не полному языку в P, сокращение лог-пространства от NL -полного языка к языку в L , оба из которые были бы языками в P, подразумевало бы маловероятное L = NL. Остается открытым вопрос, отличаются ли NP-полные задачи в отношении сокращения логарифмического пространства и полиномиального времени.

Сокращение лог-пространства обычно используется в языках P, и в этом случае обычно не имеет значения, используются ли сокращения «многие единицы» или сокращения Тьюринга , поскольку было проверено, что L, SL , NL и P все закрыты по Тьюрингу. сокращения Это означает, что сокращения Тьюринга можно использовать, чтобы показать, что проблема находится в любом из этих классов. Однако другие подклассы P, такие как NC, не могут быть закрыты сокращениями Тьюринга, поэтому необходимо использовать сокращения «многие единицы». .

Точно так же, как сокращения полиномиального времени бесполезны в P и его подклассах, сокращения логарифмического пространства бесполезны для различения проблем в L и его подклассах; в частности, каждая непустая и неполная задача в L является тривиально L- полной при редукции лог-пространства. Хотя существуют и более слабые сокращения, они не часто используются на практике, поскольку классы сложности, меньшие, чем L (то есть строго содержащиеся или считающиеся строго содержащимися в L), получают относительно мало внимания.

Инструменты, доступные разработчикам сокращения пространства журналов, были значительно расширены в результате того, что L = SL; см. в SL список некоторых SL-полных задач, которые теперь можно использовать в качестве подпрограмм для сокращения пространства журнала.

Ссылки

• Арора, Санджив ; Барак, Боаз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN  978-0-521-42426-4 . Збл   1193.68112 .

Дальнейшее чтение

• Пападимитриу, Христос (1994). «Глава 8: Сокращение и полнота». Вычислительная сложность (1-е изд.). Эддисон Уэсли. стр. 159–180 . ISBN  0-201-53082-1 . Збл   0833.68049 .