From: Cole Kitchen (kitchenc@mindspring.com)
Date: Sun Oct 27 2002 - 23:49:34 MST
Computers with closed timelike curves can solve hard problems
Authors: Todd A. Brun (Institute for Advanced Study)
(nine-page paper)
"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."
Link:
http://arXiv.org/abs/gr-qc/0209061
(It might occur to the reader of the early part of the paper that the time
needed to solve a large factoring problem could exceed the lifetime of the
computer [or the universe!], so that the result would never be sent back.
Brun addresses this objection by devising a recursive algorithm that breaks
the problem into short chunks.)
P.S. For another take on the importance of fast algorithms to the
Singularity, see Charles Stross's story "Antibodies," available in his
collection TOAST: AND OTHER RUSTED FUTURES
(http://www.amazon.com/exec/obidos/ASIN/1587154137/qid%3D1035768132/sr%3D11-1/ref%3Dsr%5F11%5F1/102-9410822-5173755).
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:41 MDT