Отправить статью по E-mail Сложность вычислений с путешествиями во времени
- Авторы: Джудакизаде М.1, Бельтюков А.П.1
-
Учреждения:
- Удмуртский государственный университет
- Выпуск: Том 16, № 2 (2025)
- Страницы: 3-54
- Раздел: Теоретические основания программных систем
- URL: https://journal-vniispk.ru/2079-3316/article/view/300936
- DOI: https://doi.org/10.25209/2079-3316-2025-16-2-3-54
- ID: 300936
Цитировать
Аннотация
Эта работа рассматривает математическую модель вычислений, которая может интерпретироваться как компьютер, способный получать данные из будущих состояний своего вычислительного процесса. При определённых сочетаниях входных данных и программ такие вычисления могут становиться невыполнимыми из-за возникающих противоречий или приводить к неоднозначным результатам. Мы исследуем программы, для которых этот процесс всегда выполним и даёт однозначный результат.Показано, что при отсутствии ограничений на вычислительную сложность такие машины могут выдавать значение любого рекурсивно разрешимого предиката через фиксированное время после начала вычисления — время задержки ответа (при этом процесс вычисления должен продолжаться и после получения ответа). Если общее время работы таких машин ограничить полиномами от размера входных данных, то эти машины будут распознавать в точности языки, принадлежащие пересечению классов NP и co-NP, за постоянное время задержки ответа в таком же смысле.Рассматриваются возможные реализации такого компьютера на практике, включая анализ возможных протоколов работы с использованием квантового отжига для выбора нужного процесса. Показано, что при распараллеливании вычислительного процесса класс задач, решаемых рассматриваемыми машинами за полиномиальное время, соответствует классу PSPACE.Кроме того, исследуется режим работы, при котором эти машины имеют прямой доступ ко входным данным. В этом случае, если время работы ограничено логарифмом от размера входных данных, то класс задач, решаемых таким параллельно работающим компьютером, содержит LOGSPACE.Результаты данного исследования могут быть использованы для разработки новых принципов программирования недетерминированных вычислительных машин, в которых вместо недетерминированных выборов используется передача данных из будущего.
Об авторах
Милад Джудакизаде
Удмуртский государственный университет
Email: joudakizadeh@mail.ru
Аспирант в области искусственного интеллекта и машинного обучения, исследования сосредоточены на вычислительной сложности, машинном обучении и логике в компьютерных науках.
Анатолий Петрович Бельтюков
Удмуртский государственный университет
Email: belt.udsu@mail.ru
Доктор физико-математических наук, профессор. Научные интересы включают вычислительную сложность, классы сложности, субрекурсивные иерархии, интуиционистскую математику, конструктивные системы, механизацию доказательств, сложность доказательств, модели вычислений, субструктурные логики, слабые арифметики и логику в компьютерных науках.
Список литературы
- S. A. Cook. „The complexity of theorem-proving procedures“, Logic, automata, and computational complexity: The works of Stephen A. Cook, ed. Kapron B.C., ACM, New York, 2023, ISBN 979-8-4007-0779-7, pp. 143–152.
- R. M. Karp. „Reducibility among combinatorial problems“, 50 Years of Integer Programming 1958–2008. From the Early Years to the State-of-the-Art, eds. Jünger M., et al., Springer, Berlin–Heidelberg, 2010, ISBN 978-3-540-68274-5, pp. 219–241.
- M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences, Freeman, San Francisco, 1979, ISBN 978-0716710455, 340 pp.
- S. Aaronson. „Guest column: NP-complete problems and physical reality“, ACM Sigact News, 36:1 (2005), pp. 30–52.
- D. Deutsch. „Quantum theory, the Church–Turing principle and the universal quantum computer“, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 400:1818 (1985), pp. 97–117.
- T. A. Brun. „Computers with closed timelike curves can solve hard problems efficiently“, Foundations of Physics Letters, 16:3 (2003), pp. 245–253.
- S. Aaronson, J. Watrous. „Closed timelike curves make quantum and classical computing equivalent“, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465:2102 (2009), pp. 631–647.
- Ch. Papadimitriou. Computational Complexity, Addison-Wesley, Reading, Massachusetts, 1994, ISBN 978-0201530827, 523 pp.
- S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, New York, 2009, ISBN 978-0521424264, 594 pp.
- M. A. Nielsen, I. L. Chuang. Quantum computation and quantum information, Cambridge University Press, New York, 2010, ISBN 9781107002173, 702 pp.
- L. K. Grover. „A fast quantum mechanical algorithm for database search“, STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (22–24 May 1996, Pennsylvania, USA), ACM, New York, 1996, ISBN 978-0-89791-785-8, pp. 212–219.
- P. W. Shor. „Algorithms for quantum computation: discrete logarithms and factoring“, Proceedings 35th Annual Symposium on Foundations of Computer Science (20–22 November 1994, Santa Fe, NM, USA), IEEE, 1994, ISBN 0-8186-6580-7, pp. 124–134.
- A. W. Harrow, A. Montanaro. „Quantum computational supremacy“, Nature, 549:7671 (2017), pp. 203–209.
- K. Iqbal, O. Ahmad, A. Y. Vandika. „Quantum computing and its implications for complex system analysis“, Research of Scientia Naturalis, 1:5 (2024), pp. 238–247.
- J. I. Orlicki. Time-travelling Turing Machines and the self-consistent Halting Problem, 2024.
- K. Gödel. „An example of a new type of cosmological solutions of Einstein's field equations of gravitation“, Rev. Mod. Phys., 21:3 (1949), pp. 447–450.
- D. Bacon. „Quantum computational complexity in the presence of closed timelike curves“, Phys. Rev. A, 70:3 (2004), 032309.
- D. H. Wolpert. „Physical limits of inference“, Physica D: Nonlinear Phenomena, 237:9 (2008), pp. 1257–1281.
- A. D. King, J. Raymond, T. Lanting, R. Harris, A. Zucca, F. Altomare, A. J. Berkley, K. Boothby, S. Ejtemaee, C. Enderud, E. Hoskinson, Sh. Huang, E. Ladizinsky, A. J. R. MacDonald, G. Marsden, R. Molavi, T. Oh, G. Poulin-Lamarre, M. Reis, Ch. Rich, Y. Sato, N. Tsai, M. Volkmann, J. D. Whittaker, J. Yao, A. W. Sandvik, M. H. Amin. „Quantum critical dynamics in a 5,000-qubit programmable spin glass“, Nature, 617:7959 (2023), pp. 61–66.
- G. L. Miller. „Riemann's hypothesis and tests for primality“, STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computing (5–7 May 1975, Albuquerque, New Mexico, USA), ACM, New York, pp. 234–239.
Дополнительные файлы
