Сколько времени распознавать палиндромы в логарифмическом пространстве?

20

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

Можем ли мы распознать палиндромы за линейное время многолентовой машины Тьюринга, используя только логарифмическое пространство? В более общем смысле, какой компромисс между пространством и временем известен палиндромам?

Bruno
источник

Ответы:

22

Используя пересекающиеся последовательности или сложность связи, легко получить компромисс между для последовательной машины Тьюринга, использующей время и пространство .T(n)S(n)=Ω(n2)O(T(n))O(S(n))

Этот результат был впервые получен Аланом Кобхэмом с использованием скрещивающих последовательностей в статье. Проблема распознавания для множества совершенных квадратов, появившаяся в SWAT (позднее FOCS) 1966.

Кристоффер Арнсфельт Хансен
источник
25

Вы можете использовать тот же аргумент, который использовался для доказательства времени на одной ленте.Ω(n2)

Предположим, что у вас есть TM с пространством которое распознает палиндромы (где является обратным ) во время . Когда (входная) головка пересекает середину она может нести только битов информации. Так что нужно сделать крестики , а каждый крест требует времени.S(n){x0n3xR|x|=n/3}xRxT(n)0n/3S(n)Ω(n/S(n))n/3

Так что .T(n)S(n)=Ω(n2)

Марцио де Биаси
источник
Опс ... после написания ответа я увидел, что Кристоффер уже выложил решение. Принимая его ответ, я оставляю свой только потому, что в нем есть еще несколько деталей.
Марцио де Биаси,
5
Я думаю, это было практически одновременно.
Кристоффер Арнсфельт Хансен
Как ты и предположил, я принял ответ Кристоффера, так как он был немного раньше ... Спасибо вам обоим!
Бруно
1
{x0n3xR|x|=|y|=n/3} выглядит странно. Лучше примечание о том, что является оператором обращения строки. {x0n3xR|x|=n/3}R
miracle173
2

В дополнение к другим ответам, стоит отметить, что, если рандомизация разрешена, палиндромы могут быть распознаны с O (1) пробелом и O (n) временем, хэшируя левую сторону строки, хешируя транспонирование правой стороны строка и проверка, равны ли хэши. Это не должно быть сложно сделать на машине Тьюринга.

пельмени мобиус
источник