Теоретические основания программных систем

Научная статья

Сложность вычислений с путешествиями во времени

Милад Джудакизаде¹, Анатолий Петрович Бельтюков²

1,2	Удмуртский государственный университет, Ижевск, Россия
2	belt.udsu@mail.ru

Аннотация. Эта работа рассматривает математическую модель вычислений, которая может интерпретироваться как компьютер, способный получать данные из будущих состояний своего вычислительного процесса. При определённых сочетаниях входных данных и программ такие вычисления могут становиться невыполнимыми из-за возникающих противоречий или приводить к неоднозначным результатам. Мы исследуем программы, для которых этот процесс всегда выполним и даёт однозначный результат.

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

Рассматриваются возможные реализации такого компьютера на практике, включая анализ возможных протоколов работы с использованием квантового отжига для выбора нужного процесса. Показано, что при распараллеливании вычислительного процесса класс задач, решаемых рассматриваемыми машинами за полиномиальное время, соответствует классу PSPACE.

Кроме того, исследуется режим работы, при котором эти машины имеют прямой доступ ко входным данным. В этом случае, если время работы ограничено логарифмом от размера входных данных, то класс задач, решаемых таким параллельно работающим компьютером, содержит LOGSPACE.

Результаты данного исследования могут быть использованы для разработки новых принципов программирования недетерминированных вычислительных машин, в которых вместо недетерминированных выборов используется передача данных из будущего. (Связанные тексты статьи на английском и на русском языках).

Ключевые слова: Машина Тьюринга, вычислительная сложность, рекурсивные множества, недетерминированные вычисления, квантовый отжиг, машина времени, искусственный интеллект

Для цитирования: Джудакизаде М., Бельтюков А. П. Сложность вычислений с путешествиями во времени // Программные системы: теория и приложения. 2025. Т. 16. № 2. С. 3–54. (Англ., Рус.). https://psta.psiras.ru/2025/2_3-54.

Полный текст двуязычной статьи (PDF): https://psta.psiras.ru/read/psta2025_2_3-54.pdf (клик по флажку в верхнем колонитуле переключит язык страницы).

Статья поступила в редакцию 15.03.2025; одобрена после рецензирования 02.04.2025; принята к публикации 02.04.2025; опубликована онлайн 21.04.2025.