Доказательство языка в Space Complexity

Question

Я хотел бы знать, правильная ли у меня интуиция и правильный ли мой ответ.

Мне дана функция $ f = {0, 1 }^* rightarrow {0, 1 }^* $, который вычисляется в пространстве $ o ( log n) $, предположим, что за каждый $ x in {0, 1 }^*$, $ f $, сохранение длины, $ | f (x) | = | x | $.

Определите $$ l = left {x #y mid x, y in {0, 1 }^*, | x | = | y |, text {и} f (x) = f (y) right } $$

Я предполагаю доказать, что $ L \in {\sf DSPACE}(\log n) $.

Пожалуйста, поправьте меня, если моя интуиция неверна.

Моим решением было бы построить решающее устройство $M$, которое является машиной Тьюринга.

$M$ принимает входные данные $x$ и $y$, запускает функцию $f$ на входных данных $x$ и $y$ и, если длины двух строк равны, принимается, в противном случае отклоняется.

Теперь машина Тьюринга работает в $ o ( log n) $, потому что функция $ f $ вычисляется в $ o ( log n) + o ( log n) = o ( log n) $ и сравнение возвращаемой длины Под функцией является $ o (1) $, поэтому язык определяется машиной Тьюринга, которая запускается в $ O ( log n) $ и занимает только место $ O ( log n) $.

Answer 1

Вот примерная идея, как это решить.Вы сравниваете $f(x)$ и $f(y)$ посимвольно.Ваша лента разделена на 4 части.Первый предназначен для моделирования $f(x)$, второй для $f(y)$, тогда у вас есть две части: одна подсчитывает, какой символ $x$ вы сейчас вычисляете, а другая $O(\log n)$ область, которая поможет вам ориентироваться.Теперь программа выглядит так

1. Определите $|x|$ и $|y|$ (сохраните их в двоичном формате!) и проверьте, совпадают ли они.
2. Вычислите первый символ $f(x)$, смоделировав его на своей машине.Сохраните вывод в TM-состоянии.Приостановите вычисление $f(x)$.
3. Сделайте $|x|+1$ шаг вправо.
4. Имитируйте $f(y)$, пока не получите первый символ, проверьте, совпадает ли он с началом $f(x)$, если нет, отклоните, в противном случае продолжайте.
5. Пройдите $|x|$ шагов влево.
6. Повторите шаги 2.-5.пока вы полностью не проверите $f(x)=f(y)$.

Answer 2

Боюсь, вы неправильно прочитали вопрос. Это размеры $ x $ и $ y $, которые должны быть равными, а не $ f (x) $ и $ f (y) $. Конечно, в этом случае, так как $ f $ является сохранением длины, $ | x | = | y | $ - это то же самое, что $ | f (x) | = | f (y) | $. Но что тогда во второй части, $ f (x) = f (y) $?

Еще одна причина, по которой ваш алгоритм не работает, заключается в том, что он использует линейное пространство. Вычисление функции $ f $ занимает логарифмическое пространство, но выход займет линейное пространство. Так что, если вы храните $ f (x) $ и $ f (y) $ на рабочей ленте, вы используете Space $ theta (n) $, а не $ o ( log n) $.