Завершенные проблемы для $ dspace ( log (n)^k) $

Question

Мы знаем, что $ polyl $ -hierarchy не имеет полных проблем, так как она противоречит теореме космической иерархии. Но есть ли полные проблемы для каждого уровня этой иерархии?

Чтобы быть точным: имеет ли класс $ dspace ( log (n)^k) $ полные проблемы под $ l $-mreductions для каждого $ k> 0 $?

Answer 1

Стандартное доказательство теоремы космической иерархии основано на космическом моделировании машин Тьюринга. Если я не ошибаюсь, это симуляция подразумевает, что для каждой конструктивной космической функции функции фланг: ℕ → ℕ, следующая проблема в DSPACE (фланг(не)) (куда не Длина ввода):

Учитывая кодирование детерминированной машины Тьюринга М с входной лентой только для чтения и рабочей лентой с чтением с фиксированной рабочей алфавитом (например, {0, 1, blank}), строка Икс, и подсчет строки 1^Т, Решите, если М остановка на входной строке Икс Прежде чем использовать больше, чем фланг(Т) Рабочее пространство.

Эта проблема - dspace (фланг(не))-жестко под логическим пространством много-один-один. Вот доказательство в случае фланг(не) = LG^kне. Анкет Для каждого языка Л∈Space (log^kне), есть машина Тьюринга М (из формы, изложенной выше), которая принимает Л в в LG^kне пространство для некоторых в∈ℕ. Модифицировать М к М′ Так, когда М отвергает, М′ Вместо этого переходит в бесконечную петлю. Затем с учетом входной строки Икс, позволять Т = |Икс|^в, и мы генерируем экземпляр (М′, Икс, 1^Т) проблемы выше. (Я думаю, что единственная слегка нетривиальная часть заключается в том, что мы не можем установить Т = |Икс|.)

Поэтому эта проблема - dspace (фланг(не))-заполнить под логическим пространством много-один-один.

Answer 2

Просто уколинный комментарий.

В газете "Проблема пустоты для пересечений обычных языков«Показывается, что решение о том, как пустота пересечения языков, признанных $ g (n) $ dfas, завершено для $ nspace (g (n) log {n}) $;, в частности, пустота пересечения Языки, расположенные $ log^{k-1} {n} $ dfas завершен для $ nspace (log^{k} {n}) $, $ k geq 1 $.

Но кажется, что тот же результат не может быть ограничен DPSACE, если мы рассмотрим пересечение пустоты языков, признанных $ g (n) $ tally-dfas (DFAS только с одним символом в алфавите).

Однако $ hightset = bigcap^k dfa_ {lin} $ завершена для $ dspace ( log {n}) $ для каждого $ k $.