Как вычислить палиндром из потока символов в сублинейном пространстве / времени?

Я даже не знаю, существует ли решение или нет. Вот проблема в деталях. Вы - программа, которая принимает бесконечно длинный поток символов (для простоты можно предположить, что символы равны 1 или 0). В любой момент Я могу остановить поток (скажем, после того, как прошли N символов) и спросить вас, является ли полученная строка палиндромом или нет. Как вы можете сделать это, используя меньше сублинейного пространства и / или времени.