Complexity of computations with time travel

Эта работа рассматривает математическую модель вычислений, которая может интерпретироваться как компьютер, способный получать данные из будущих состояний своего вычислительного процесса. При определённых сочетаниях входных данных и программ такие вычисления могут становиться невыполнимыми из-за возникающих противоречий или приводить к неоднозначным результатам. Мы исследуем программы, для которых этот процесс всегда выполним и даёт однозначный результат.
Показано, что при отсутствии ограничений на вычислительную сложность такие машины могут выдавать значение любого рекурсивно разрешимого предиката через фиксированное время после начала вычисления — время задержки ответа (при этом процесс вычисления должен продолжаться и после получения ответа). Если общее время работы таких машин ограничить полиномами от размера входных данных, то эти машины будут распознавать в точности языки, принадлежащие пересечению классов NP и co-NP, за постоянное время задержки ответа в таком же смысле.
Рассматриваются возможные реализации такого компьютера на практике, включая анализ возможных протоколов работы с использованием квантового отжига для выбора нужного процесса. Показано, что при распараллеливании вычислительного процесса класс задач, решаемых рассматриваемыми машинами за полиномиальное время, соответствует классу PSPACE.
Кроме того, исследуется режим работы, при котором эти машины имеют прямой доступ ко входным данным. В этом случае, если время работы ограничено логарифмом от размера входных данных, то класс задач, решаемых таким параллельно работающим компьютером, содержит LOGSPACE.
Результаты данного исследования могут быть использованы для разработки новых принципов программирования недетерминированных вычислительных машин, в которых вместо недетерминированных выборов используется передача данных из будущего.