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