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

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

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

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

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

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

Примечания

  1. ^ Арора и Барак (2009) стр. 88

Рекомендации

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

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