[FOM] why should we, in computer science, be excited about the possibility of speeds exceeding speed of light

[Kreinovich, Vladik]

Dear Friends, 

You may have heard about a recent experimental re-confirmation of neutrinos traveling faster than light; see, e.g., 
http://www.nature.com/news/neutrino-experiment-replicates-faster-than-light-finding-1.9393
While this confirmation is not final and doubts remain, you may have seen speculations about the possibility of time traveling to the past, about the related paradoxes of time travel, etc. You may have been curious about this interesting physical phenomenon, but most of you are probably not relating it to computing. 

Actually, we computer scientists should be following these experiments with even larger interest than physicists. Indeed, the relation between computing and acausal processes has been analyzed in the past, and the conclusion is as follows. If such faster-than-light acausal processes indeed exist, then: 

* On the one hand, the time travel paradoxes will most probably indeed prevent actual time travel (so do not yet buy tickets to the past :-(). In other words, new physics will emerge but not as revolutionary as some journalists make us believe. 

* On the other hand, acausal processes can potentially lead to a drastic computation speed-up -- including the possibility of solving NP-hard problems in polynomial time. In other words, new computations can emerge. 

(see a short explanation below, with references to more detailed papers). 



***********************************************************************************************************************From the 2004 paper 

Vladik Kreinovich and Luc Longpre, "Fast Quantum Algorithms for Handling Probabilistic and Interval Uncertainty",
Mathematical Logic Quarterly, 2004, Vol. 50, No. 4/5, pp. 507-518.
http://www.cs.utep.edu/vladik/2003/tr03-22c.pdf 

"Several physical theories have led to the appearance of closed timelike curves, the possibility to go back in time. Suffice it to say that one of the
main ideas which helped R. Feynman to develop a modern version of quantum electrodynamics was the idea of
positrons as electrons going back in time. Until the late 1980s, these possibilities were largely dismissed by
mainstream physics as mathematical artifacts which cannot lead to actual going back in time. Only when Kip
Thorne, the world's leading astrophysicist, published several papers on acausal solutions in Physical Reviews, the
topic became more mainstream.

Reasonable solutions with causal anomalies were discovered in many physical theories. For example, in
general relativity, the curved space-time generated by a sufficiently massive cylinder that rotates sufficiently fast
contains a closed timelike curve (causal anomaly). In string theory, a theory that describes elementary particles
as non-point objects ("strings"), seemingly interactions between such particles sometime lead to the possibility to
influence the past (i.e., to a causal anomaly). It was also shown that modern cosmological theories, in which the
current cosmological expansion is preceded by a short period of exponentially fast growth ("inflation"), also lead
to the possibility of a causal anomaly. An interested reader can find the detailed description of these causal
anomalies, e.g., in Kip Thorne's book and in the papers referenced in this book.

The main obstacle to accepting acausal phenomena used to be paradoxes associated with time travel. These
paradoxes can be illustrated on a commonsense example of a "father paradox": a time traveler can go to the past
and kill his father before he himself was conceived, thus creating a paradox. The accepted solution to the acausal
paradoxes can also be illustrated on the "father paradox" example: since the time traveler was born, this means
that some unexpected event prevented him from killing his father. Maybe a policeman stopped him, maybe his
gun malfunctioned. Even if the time traveler takes care of all such probably events, there are always events with
small probability - like a meteor falling on the traveler's head - which cannot all be avoided. Thus, all we will
achieve if we try to implement a paradox is that some event with a very low probability will occur.

There are several ways to use acausal processes in computing. The trivial way is to let a computer run a long
program for whatever it takes and then send the results back in time. A less trivial way of saving time is similar
to quantum "computing without computing" - speeding up without actually using time machines. This method
was originally proposed in Kosheleva et al. 1981; see also Maslov 1987, Moravec 1991, Koshelev 1998. This method is related to the above solution to the father paradox. Indeed, to solve, e.g., a propositional satisfiability problem with n variables, we generate n random bits and check whether they satisfy a given formula; if not, we launch a time machine that is set up to implement a low-probability event (with some probability p0 << 1). Nature has two choices: either it generates n variables which satisfy the given formula (probability of this is 2^(-n)), or the time machine is used which leads to an event with a probability p0. If 2^(-n) << p0, then statistically, the first event is much more probable, and so, the solution to the satisfiability problem will actually be generated without the actual use of a time machine."

Koshelev M. (1998). "Maximum entropy and acausal processes: astrophysical applications and challenges", In: G. J.
Erickson et al. (eds.), Maximum Entropy and Bayesian Methods, Kluwer, Dordrecht, 253-262.

M. Koshelev and V. Kreinovich, "Towards Computers of Generation Omega - Non-Equilibrium Thermodynamics, Granularity, and Acausal Processes: A Brief Survey", Proceedings of the International Conference on Intelligent Systems and Semiotics (ISAS'97), National Institute of Standards and Technology Publ., Gaithersburg, MD, 1997, pp. 383-388.
http://www.cs.utep.edu/vladik/1997/tr97-12.pdf

Thorne K. S. (1994). "From black holes to time warps", W.W. Norton, N.Y.

Moravec H. (1991). "Time travel and computing", Carnegie-Mellon Univ., CS Dept. Preprint.

Maslov S. Yu. (1987). "Theory Of Deductive Systems And Its Applications", MIT Press, Cambridge, MA.

Kosheleva O. M., Kreinovich V. (1981). "What can physics give to constructive mathematics", In: Mathematical Logic
and Mathematical Linguistics, Kalinin, Russia, 117-128 (in Russian).

Feynman R. P. (1949). "The theory of positrons", Physical Review, vol. 76, 749-759.