Является ли DSPACE (n) = DSPACE (1,5n)?

Из теоремы о пространственной иерархии известно, что если конструируемо в пространстве, то DSPACE ( ) не равно DSPACE ( .$f$2 f ( n ) f ( n ) )$2f(n)$$f(n))$

Здесь под DSPACE ( я подразумеваю класс всех задач, которые могут быть решены в пространстве машиной Тьюринга с некоторым фиксированным алфавитом. Это позволяет с такой точностью рассматривать теорему о пространственной иерархии.$f(n))$$f(n)$

Стандартный аргумент дает мультипликативную константу : нам нужно пространство для построения вычисления некоторой машины Тьюринга с помощью универсальной. Также нам нужно чтобы решить проблему с остановкой.$2$$f(n)$$f(n)$

Вопрос: Является ли DSPACE ( ) , равная DSPACE ( )? $f(n)$3$\frac{3}{2}f(n)$

Можно доказать, что DSPACE $(f(\frac 32 n))\ne$ DSPACE$(f(n))$если$f$растет хотя бы линейно, используя простой вариант стандартного аргумента заполнения. Для языка$L$пусть$L'=\{x0^{|x|/2}\mid x\in L\}$.

Запрос. $L\in$ DSPACE $(f(n))$ тогда и только тогда, когда $L'\in$ DSPACE $(f(\frac 23n))$если$f(n)\ge \frac 32n$.

(Мой первый ответ содержал несколько неправильных утверждений, спасибо Эмилю за то, что он это заметил.)

Сначала я покажу, как использовать утверждение, чтобы доказать иерархию. Поскольку $f$ растет хотя бы линейно, имеем DSPACE $(2f(n))\subset$ DSPACE $(f(2n))$ . Возьмем язык $L\in$ DSPACE $(f(2n))\setminus$ DSPACE $(f(n))$ . Используя утверждение, $L'\in$ DSPACE $(f(\frac 43 n))=$ DSPACE$(f(n))$, где последнее равенство является косвенным предположением. Но тогда$L\in$DSPACE$(f(\frac 32 n))=$ DSPACE$(f(n))$, где последнее равенство снова по косвенному предположению, что дает противоречие.

Доказательство претензии. Если $L'\in$ DSPACE $(f(\frac 23 n))$, то для доказательства$L\in$DSPACE$(f(n))$нам просто нужно написать$|x|/2$0 до конца ввода$x$и моделируют машину, которая приняла$L'$. Поскольку$f(n)\ge \frac 32 n$, это не увеличит пространство, которое мы используем. (На самом деле, зная, сколько писать 0, совсем не ясно, если$f$мало и мы не можем увеличить размер алфавита - вместо этого мы можем использовать другую ленту и записать на нее все, что будет после конца$x$.)

Другое направление - это просто, заменяя 0 на *, если нам разрешено писать *. (См. Проблемы с этим в моем комментарии к вопросу.) Если нам не разрешено писать звезды, мы слегка модифицируем определение $L'$ как $L'=\{x10^{|x|/2}\mid x\in L\}$ . Теперь вместо записи звезд мы сохраняем исходный ввод $x10^{|x|/2}$и работать с этим. Но когда мы достигаем 1, мы идем вправо, пока не нажмем еще 1, чтобы проверить, был ли это конец слова 1 или нет. Если мы нашли еще одну 1, мы просто вернемся к нашей 1. Если мы не нашли, мы все еще вернемся, но мы будем знать, что ее следует рассматривать как звезду - если мы будем писать на ней, то мы также пишем 10 после него, чтобы иметь новый маркер конца текущего слова. (На самом деле, в этой части также есть небольшая загвоздка, если $f$ мало - как мы можем проверить, имеет ли вход форму $x10^{|x|/2}$ ? Без уничтожения ввода я могу решить эту проблему, используя несколько головок для малого $f$ .)