Email this article Complexity of Computations with Time Travel
- Authors: Joudakizadeh M.1, Beltiukov A.P.1
-
Affiliations:
- Udmurt State University
- Issue: Vol 16, No 2 (2025)
- Pages: 3-54
- Section: theoretical computer science
- 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
Cite item
Abstract
This paper explores a mathematical model of computation that can be interpreted as a computer capable of receiving data from future states of its own computational process. Under certain combinations of input data and programs, such computations may become infeasible due to emerging contradictions or lead to ambiguous outcomes. We investigate programs for which this process is always feasible and yields a unique result.It is demonstrated that, in the absence of computational complexity constraints, such machines can output the value of any recursively decidable predicate within a fixed time after the computation begins—referred to as the response delay time—while the computation process must continue even after the result is produced. When the total runtime of these machines is bounded by a polynomial function of the input size, they precisely recognize languages belonging to the intersection of the NP and co-NP complexity classes, with the same constant response delay time in the aforementioned sense.Possible practical implementations of such a computer are examined, including an analysis of operational protocols leveraging quantum annealing to select the appropriate computational process. It is shown that, with parallelization of the computational process, the class of problems solvable by these machines in polynomial time corresponds to the PSPACE complexity class.Additionally, a mode of operation is studied in which these machines have direct access to input data. In this case, if the runtime is limited to a logarithmic function of the input size, the class of problems solvable by such a parallelized computer encompasses LOGSPACEThe findings of this study can be applied to develop new programming principles for nondeterministic computational machines, where data transmission from the future is employed instead of nondeterministic choices.
About the authors
Milad Joudakizadeh
Udmurt State University
Email: joudakizadeh@mail.ru
PhD student in Artificial Intelligence and Machine Learning, Research focuses on computational complexity, machine learning, and logic in computer science.
Anatoly Petrovich Beltiukov
Udmurt State University
Email: belt.udsu@mail.ru
Doctor of Physics and Mathematics, Professor. Research focuses on computational complexity, complexity classes, subrecursive hierarchies, intuitionistic mathematics, constructive systems, proof mechanization, proof complexity, computation models, substructural logics, weak arithmetics, and logic in computer science.
References
- 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.
Supplementary files
