It is a common trope in sci-fi that engaging a vessel's faster-than-light travel requires performing some complicated mathematics that takes a non-trivial amount of time.
I want to know to what extent this is even remotely plausible. In other words: what time-complexity is reasonably implicated by any arbitrary form of FTL?
After all, in my own (limited) experience, almost all calculations typically fall into one of two categories:
- Any everyday computer can complete it in a fraction of a second. I think that's pretty much all of arithmetic, algebra, geometry, ballistics, and calculus. Effectively zero time.
- No single computer has any realistic chance of performing the computation in less than several hours. E.g. video transcoding, defeating some forms of cryptography. For someone fleeing for their life, this is effectively "infinite time."
Of course, I'm aware that there are problems that would take more time (and energy) to solve than exists in the universe.
The obvious challenge here is that we don't have FTL, and I'm not going to describe a specific system and ask you to analyze it. What I propose instead is to enumerate some observable characteristics that are common to a variety of popular fictional FTL systems, and then to reason about their time complexity.
First, let's talk about the observed characteristics of the FTL systems I have in mind.
Whether you're talking about Star Wars' hyperdrive, or Battlestar Galactica's FTL, or probably any of a dozen less well-known variants, the calculation cannot be prepared in advance. It must be performed immediately prior to the FTL transit.
Even without knowing the engineering particulars, there are a couple of obvious reasons why this might be the case: some of the terms in the equations depend on the point of departure, or are time-sensitive, i.e. if your destination is something in motion, like a planet or star, you can't calculate its position without also specifying a time.
And so the most straightforward approach is to read the current values from the environment. Of course, this isn't why writers do it: they do it because it's a low-effort way to manufacture a ticking clock when you want suspense. But this is the putative justification, and indeed it sometimes gets mentioned by characters.
Another thing that's almost universally true is that there is no complementary calculation for how to shut down the FTL; I don't think I've ever seen something like that. This is true whether the transit is instantaneous (as in BSG) or not (as in SW). And if there is any math that must be performed during the transit (e.g. in Star Trek, the computer monitors the warp field and propulsion system to make continuous adjustments), it doesn't impact departure or arrival in any way that we see.
Also, I am talking about the math only. It's often the case that the FTL system must "warm up" (or "cool down" from the previous transit), and that takes time too, but these are always presented as orthogonal concerns. Presumably, the math can be performed whether or not the drives are ready; you could even do the math just for fun, and not actually execute the transit once you have the solution. I only care about the time required by the math.
Second, let's talk about some constraints.
It's obviously impossible to evaluate the time-complexity of a set of problems if I don't specify those problems. However, I think we can reasonably exclude a lot of territory.
For one: while there may be a huge class of problems that are either literally unsolvable by computers (e.g. the halting problem), or not solvable within a useful time (e.g. cracking AES-256), it seems self-evident that nobody would actually put these systems into a multitude of vessels if it was reasonably likely that very many FTL transits would fail to compute within a reasonable timeframe.
If we had a machine today that could take us to the stars at faster-than-light speed, but it had the same time complexity as cracking AES, we might actually build a few of them and turn them on, because even though the likelihood of near-term success is low, the potential payoff is enormous. But we wouldn't put one of those in every single spaceship. And nobody who is fleeing from combat would consider that device to be their best chance of escape; they probably wouldn't even turn it on. If the math for a jump isn't known to be "in P," people wouldn't rely on FTL as primary transportation. Not even for shipping freight:
"I'm hauling 20 tons of frozen bananas to Alpha Centauri. We could arrive any time between 5 minutes and 1053 years from now, so don't wait up." -- ≠P Space trucker
Thus, I think we can say with absolute certainty that the whole class of FTL drives relies on math that is known to be solvable in polynomial time.
I think we can say more: it seems probable that the bulk of any computation will take place in the domain of navigation. So, I'd expect to see a lot of arithmetic and trigonometry. Possibly there might be some physics simulation, which I assume involves calculus. Perhaps some database access to help determine the positions of known, distant objects.
The problem for me is that all of this falls into the category of "easily solvable in milliseconds on current-day hardware." And it's ludicrous to suppose that a civilization where FTL is commonplace would have worse computers than we do. Moreover, even if we're talking about computational expenses similar to video transcoding, which (depending on the input) can take hours, it's absurd to think that (1) the civilization wouldn't develop specialized hardware to solve those problems quickly, and (2) individual vessels wouldn't purchase whatever extra hardware is needed to further reduce the computation time to zero. We do transcoding in the cloud; Han Solo would buy 10 fancy graphics cards and a 64-core CPU, because the alternative is death or imprisonment if he can't bug-out at the drop of a hat. Nobody is going to fly around with the slow factory model of jump CPU if they can upgrade. And if "calculation" is an accurate description of what is being done, very significant upgrades will necessarily be possible.
And let's be realistic: the FTL calculation is not going to include actually transcoding a video, because that is obviously irrelevant to travel. It's not going to use deliberately-expensive computation (like bcrypt), because nobody wants the FTL to take longer than necessary.
So, it seems to me, by the light of my dim understanding of computation theory, coupled with reasonable expectations about pilot behavior, that any version of FTL that requires pre-departure math would necessarily lead to one of exactly two scenarios:
- FTL is not solvable in polynomial time, is therefore not even remotely practical, and so would not be part of most vessels; or
- FTL is solvable in polynomial time, vessels will optimize it to death, and so the oft-seen countdown has no basis
I'm not well-versed in computation theory, and I'm sure there are people here with a better grasp of NP-completeness than I. And probably there are additional meta-mathematical domains that are relevant of which I'm not aware.
So, what I'm asking for is:
Within the boundaries of the observed FTL characteristics I've described, and without manufacturing some set of time-consuming handwavium computations -- that is, without inventing a specific system, what are the narrowest boundaries we can reasonably place on the amount of time it would take to calculate the endpoints of an FTL transit, and/or plot a course between them through spacetime?
Put another way: can you identify any problem domain that would necessarily be part of the whole family of "math before jump" FTL, that has many problems which are not solvable in polynomial time, or which couldn't eventually be optimized down to <1 second?
I take both of those questions to be formulations of the same concern, so answers must survive both.