Skip to main content
SpringerLink
Log in

Computers with Closed Timelike Curves Can Solve Hard Problems Efficiently

  • Published:
Foundations of Physics Letters

Abstract

A computer which has access to a closed timelike curve, and can thereby send the results of calculations into its own past, can exploit this to solve difficult computational problems efficiently. I give a specific demonstration of this for the problem of factoring large numbers and argue that a similar approach can solve NP-complete and PSPACE-complete problems. I discuss the potential impact of quantum effects on this result.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

REFERENCES

  1. P. W. Shor, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, S. Goldwasser, ed., pp. 124-134 (IEEE Computer Society Press, Los Alamitos, CA, 1994). An expanded version of this article is available on the preprint archive, quant-ph/9508027.

    Chapter  Google Scholar 

  2. M. S. Morris and K. S. Thorne, Am. J. Phys. 56, 395-412 (1988).

    Article  ADS  MathSciNet  Google Scholar 

  3. J. L. Friedman, M. S. Morris, I. D. Novikov, F. Echeverria, G. Klinkhammer, K. S. Thorne, and U. Yurtsever, Phys. Rev. D 42, 1915-1930 (1990).

    Article  ADS  MathSciNet  Google Scholar 

  4. I. D. Novikov, Sov. Phys. JETP 68, 439 (1989).

    Google Scholar 

  5. J. Earman, Bangs, Crunches, Whimpers, and Shrieks: Singularities and Acausalities in Relativistic Spacetimes (Oxford University Press, New York, 1995).

    Google Scholar 

  6. J. Earman, Erkenntnis 42, 125-139 (1995).

    Article  MathSciNet  Google Scholar 

  7. A. Carlini, V. P. Frolov, M. B. Mensky, I. D. Novikov, and H. H. Soleng, Int. J. Mod. Phys. D 4, 557-580 (1995).

    Article  ADS  MathSciNet  Google Scholar 

  8. M. Y. Konstantinov, gr-qc/9510039.

  9. A. Carlini, I. D. Novikov, Int. J. Mod. Phys. D 5, 445-480 (1996).

    Article  ADS  MathSciNet  Google Scholar 

  10. G. E. Romero and D. F. Torres, Mod. Phys. Lett. A 16, 1213-1222 (2001).

    Article  ADS  MathSciNet  Google Scholar 

  11. P. G. Grove, Found. Phys. 32, 567-587 (2002).

    Article  MathSciNet  Google Scholar 

  12. C. H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, 1994).

    MATH  Google Scholar 

  13. This problem is more commonly known as quantified Boolean formula (QBF); for a discussion of this problem in particular and PSPACE-complete problems in general, see [12].

    MATH  Google Scholar 

  14. S. W. Hawking, Phys. Rev. D 46, 603-611 (1992).

    Article  ADS  MathSciNet  Google Scholar 

  15. H. D. Politzer, Phys. Rev. D 46, 4470-4476 (1992).

    Article  ADS  MathSciNet  Google Scholar 

  16. S. Rosenberg, Phys. Rev. D 57, 3365-3377 (1998).

    Article  ADS  MathSciNet  Google Scholar 

  17. D. Deutsch, Phys. Rev. D 44, 3197-3217 (1991).

    Article  ADS  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Advanced Study, Einstein Drive, Princeton, New Jersey, 08540

    Todd A. Brun

Authors
  1. Todd A. Brun
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brun, T.A. Computers with Closed Timelike Curves Can Solve Hard Problems Efficiently. Found Phys Lett 16, 245–253 (2003). https://doi.org/10.1023/A:1025967225931

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1025967225931

Search

Navigation