How long can it really take to calculate a hyperspace jump?

Question

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:

1. 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.
2. 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 10⁵³ 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:

1. FTL is not solvable in polynomial time, is therefore not even remotely practical, and so would not be part of most vessels; or
2. 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.

Answer 1

An arbitrary example of a calculation with suitable complexity, that matches the complexity of a hyperdrive jump, which cannot be pre-calculated but which can be calculated and shared to multiple other people for immediate use:

Pick your starting and ending coordinates:
These coordinates are mapped on a multidimensional Fractal space. For simplicity of illustration here, I will display a 2-d image of a Mandelbrot fractal.
Just to show the infinite complexity that fractals can have.

Now calculate the exact line of equipotential between your starting point (which is fixed) and an acceptable ending point near where you want to exit.
This calculation takes a long time, but reasonably predictable time for any given parameter of accuracy.

Yes, that image is of ONE LINE around an equipotential of the Mandelbrot set.
And no, zooming in does not simplify the line. It stays at that same complexity level at 10-x, 100000-x, or googol-x zoom.

No, you cannot precalculate this, as the exact shape of the fractal will vary depending on current interstellar relative positions, energy densities, and gravitic events (like the "bounce too close to a supernova" that Han mentions). As conditions change, the fractal representation of the hyperspace manifold changes.
But, once calculated for current conditions, start position and desired end position, the solution will remain valid unless conditions change. This allows you to share your calculation to your fleet, allowing coordinated movement.

A planetary-scale computing complex might precalculate a few million possible variations of conditions, for a known set of start and end points in the very near future, allowing smaller ships without the needed computers to do a jump. But the number of precalculations would depend on the number of independent variables, which are likely to be many.

This is an example of a very computationally intensive problem, that requires a reasonably consistent amount of time to calculate to a given precision level. And cannot practcally be precomputed and stored in a database.

P.S. The OP's example of video transcoding is actually a pretty good example of a suitable problem!
It is a huge, finite, and quite accurately time-predictable task which is utterly dependent on input data, parameters, and desired output. The reason it takes OP "hours", is because they have chosen that as an acceptable trade-off point between quality and time. The same task could be performed in seconds, for a very low-resolution version of the video, or decades, for an ludicrously ultra-high resolution video stream.

Answer 2

Simulation of the galaxy.

When you're doing FTL jump, thanks to the lightspeed lag, you are always operating on the information about your target system that's outdated from years to decades and centuries.

Normally a star would travel a cosmically insignificant distance in this time, but you don't want to pop up "somewhere in the general vicinity" of the star, you want to pop up inside the planetary system, or even right on a suitable orbit around a planet. So you need to predict the position of the destination right now based on this outdated information, and do it to a precision with an acceptable error margin of several thousands of kilometers. Considering the complexities of gravitational interactions in an n-body system, you need to model interactions of thousands to millions of objects, since the errors in calculations, however small they might be, can be enough to displace you millions of kilometers away from your destination, or if you had bad luck, put you inside of it. So you need to essentially simulate the movement of a small chunk of the Milky Way, along with every significant source of gravity in it interacting with every other source - like stars, planets and nebulae (hello fluid simulations). And to do that, you need to simulate backward the stars around you first, based on their distance to you and data from your observatory module, to find their needed objective positions at the start of the simulation.

It sounds like "hours to days to complete on a mainframe computer" type of problem, but extrapolating this into future sounds like a worthy task for a futuristic navigation computer of a spaceship would think over for several minutes. You can't optimize this task, because any optimization would invoke simplifications and approximations, the very thing you don't want to have when calculating your arrival point and velocity.

The "less you spend on calculations - the dirtier and more imprecise your arrival is" can even be a good plot point.

Answer 3

Chess.

from https://chess.stackexchange.com/questions/2422/database-of-every-possible-move-in-chess

I believe your question essentially boils down to the topic of whether it is possible to completely "solve" chess. Wikipedia has an excellent article on the topic which should give you a good overview.

To summarise, the number of possible game variations in chess is estimated to be 10^120. This is a staggeringly huge number, for comparison, consider that the number of atoms in the observable universe is estimated to be around 10^80. In other words, if you were using the entire observable universe as your hard drive, you'd still need to store 10^40 combinations of chess games on each atom, in order to simply store it all. Needless to say, this is so far beyond our current and forseeable technologies that most people consider it to be completely impossible.

Assume that modelling a hyperspace jump is like modelling a chess game except there are more pieces. Given the initial set up of the relevant universe, the computer runs multiple jumps which return different probabilities of success. Some clearly have a low chance of success. The computer continues to run simulated jumps until it arrives at one with an acceptable chance of success, "acceptable" probability being something determine by circumstances. One could improve the chance of success by opening up possible destinations - for example if you are fleeing, any open space is acceptable. If you want to jump to a precise location with a high chance of success, many simulations might be necessary.

"Many" being 10^big. It can be done. It might be done pretty quick, with luck. Or not.

Answer 4

Calculation times, in practice, are often more about Human patience than computer power

Calculations can take a long time. In solid state physics people are often forced to leave a supercomputer running for weeks to simulate a quantum system, sometimes months. This is all just number stuff, adding and multiplying - its just there is a lot of it to do.

However, a crucial point is that these kinds of solid state physics simulations will always take weeks to months no matter how good our computers get. The simulation makes all kinds of approximations, you probably want a set of atoms that is "effectively infinite" but you probably only have 100 as more would slow things too much for your patience. If computers got better your patience would not change, so it would take the same time and you would have 200 atoms. Maybe there is a variable you keep fixed in all your calculations - but if the calcs ran 10 times faster you would sweep that variable to see how it changed things.

Jump times, in practice, are determined more by Human patience than computer power

Ok, but FTL navigation is different surely? Maybe in 2650AD an FTL jump takes an hour to calculate, but by 2670 the same calculation is down to 3 minutes. By 3000 AD its 2 seconds. The period in history where it falls in the middle seems likely to be short.

Unless there is another variable, something like the number of atoms above. People's patience remains the same, so on average if 1 hour is the most anyone can possibly be bothered to wait for an FTL jump (people of the future are impatient) then as computers get better people will take more of the other thing.

What is the other thing? Maybe its the size of your ship, bigger ship -> more complicated jump calculations. Then ship size and computer power scale together. Maybe the scaling is something else - perhaps each time a ship jumps it leaves ripples in the warp that make the maths harder for the other ships nearby. Suppose that if jumps take X seconds it is profitable to have more ships flying routes. More and more ships are flying until jumps take about X seconds on average and some kind of equilibrium is found. Then computers get better, but economics will ensure that any reduction in jump times will be short lived, as that extra capacity will be filled by more people jumping. (Traffic on real roads can follow a similar pattern.)

Answer 5

Okay. I have to choose my words carefully to stay off the timekeeper's radar. Also, just for starters, I can't share any of the formulae involved because they are based on 23rd century "true" math and wouldn't make any sense to your 21st century approximation of that higher nomenclature.

What is referred to as a "calculation" in your current age fiction is actually a computationally-intensive exercise in real world prediction. The task boils down to grabbing several sequential snapshots of quantum-particle level sensor data and from them calculating where every part of every particle in your immediate trajectory will be at several distinct moments in the proximal future. The gravitational and --CENSORED-- contributions of every particle to the underlying space-time must be known before it happens, for every particle in an arch forward out to the distance needed for your engines to achieve FTL (warp) or FTL-INFINITE (jump) speed. The reason for this is simple, but non-obvious until you actually start approaching these speeds. I don't have time (or editorial freedom) to go into the details, but just assume that even subatomic particle impacts become significant at near-luminal speeds.

So you are not waiting on your computer to figure out the course to your destination or some esoteric value which is needed to get universal permission to go real fast. You are waiting for your computer to find the possibly-nonexistent instance in time when the path ahead is navigable out to the distance needed to go super-luminal.

A number of factors influence this computation and none of them are known up until the moment that the FTL calculation is requested.

• You need to know how many sub-atomic particles are in your forward path which will determine how long it will take to determine where they all will be at every possible (yet to be determined) proximal future moment.
• With that calculation estimation curve established, you can then determine the specific moment in future time for which your computer should start searching for a clear launch window. This is done by adding the estimated calculation time and the engine engagement statistics (start-delay, acceleration-curve and subluminal-threshold) to the current moment, then back-tracking to allow for your ship's captain's average response time in issuing the "engage" command. (Damn Shatner for starting that wasteful two-syllable tradition. A simple "Go" would have saved millions of cpu cycles.)
• Once your computer has this all worked out, it then has to continue computing it going forward until your captain gets around to deciding to start the journey. Most of the work is already done by then, getting the whole predictive model in place and running the particle map consistently ahead of real time, but it must then be maintained, with new window moments being identified as needed until the captain is ready to go.

These factors have an obvious ramification for would-be faster-than-light adventurers...

• It works much better in deep vacuum, where the particle densities are lowest. Launch windows appear very regularly when there aren't trillions of participants in the "let's block the launch window" game. Consequently, launch windows among the inner planets are pretty rare. Too many miniscule planetary sheddings and solar discharges can really get in the way. Your best choice of departure points is out beyond the Oort cloud, but getting there in some systems can take a lifetime at sub-light.

Okay. I have offered what I can. Hope it helps. Hope I haven't said too much. As a disclaimer, none of the ideas presented here are actual scientific theories proposed by actual scientists either living or yet to be born. This answer does not violate the prohibition against early release of future information as everything stated here is purely speculative and not to be confused with actual reality. Any similarities to actual discoveries, either current or upcoming, are purely circumstantial. Please don't delete my personal timeline.

Answer 6

10 light years is about 58,786,253,700,000 miles. Assume you have to check the entire path for obstacles larger than a few metres across, as running into the hyperspace mass shadow of a 50 ton rock at multiples of the speed of light is going to jar the bolts loose, and then some! (We know from current-day experience that walking into a 40 gram bullet at a mere 1700 miles/hr is going to do some damage.) So multiply the resolution needed by a thousand or so. Then consider that the rocks and other hyperspatial anomalies are all moving in different directions at different speeds, were all measured with finite accuracy, and were probably last surveyed years ago. (As a rebel/smuggler, you want to stay off the busier and better-surveyed spacelanes with their ubiquitous Imperial police patrols.) And you also probably can't bend your trajectory too fast. (At least, not without finding your face pressed hard up against the cockpit window saying 'Gnnngh.')

So let's say you have to do a database lookup for any 'starchart' records for cells along a line 58,786,253,700,000 miles long and broad enough to include any rocks moving in from neighbouring cells down to a resolution of a few metres, project the position of every obstacle found forward to the present time (with error bars!) check for intersections, try to tweak the trajectory to avoid any hits detected, check accelerations along the new course for passenger safety/engine feasibility, and then recheck the new trajectory for obstacles.

And that's without even having to do it in ten dimensional hyperspace with exotic mathematics. The complexity of searching in three dimensions increases with the cube of the size of the region, the complexity in ten dimensions with the tenth power. So scale up by 10, and a 3D search expands by a factor of 1,000, and a 10D search expands by a factor of 10,000,000,000.

If we estimate that a 10 light year jump calculation needs to take around 100 seconds to be practical, then we have to process each thousand miles of trajectory in about 1.7 nanoseconds. That's on the order of a few clock cycles on a current-day CPU.

Space is big!

Answer 7

This is a Frame Challenge

I've enjoyed reading the many answers, but they all have one overriding problem: you're asking us to explain using today's best-guess concerning technology how we could do something that won't matter for some time into the future. I therefore question the usefulness of the answers.

• If you have the tech to fly FTL, you certainly have improved computational tech. Since we cannot but imagine the tech needed to fly FTL, it's reasonably true that we cannot but imagine the computational tech available to calculate navigation.

• Since we know nothing about flying FTL in the real world (other than we believe it can't be done), we obviously know nothing about the navigational hazards of flying FTL. We can look at the gravity wells, etc., that we know about, but how valuable can that be to you? Before we learned how to fly, the hazards of flight were basically unknown to us. We learned what they were as we improved the technology.

But more to the point, what all those SciFi shows were really doing was stepping past a bit of window dressing to continue telling their story

Over the years I've noticed that there's a number of people who perceive "hard sci-fi" as something it really isn't. They think that "hard sci-fi" is a story that rigidly adheres to science. To that end, they look for rational, scientifically complete descriptions of fanciful, Clarkean magic. I ran a publishing house for about 10 years, and one of the things I learned during that time is that new authors often got hung up in details that didn't actually relate to their story.

So, why do all those wonderful SciFi stories basically skip over the mathematics and computational reality of navigating FTL?

Because it's irrelevant.

With incredibly rare exceptions, all stories fall into one or more of the seven basic plots. Science Fiction is nothing more than the window dressing used to tell a story. Let's face it, unless you're writing a textbook about the history of some aspect of science or your writing an article postulating the possible future developments of said aspect, what you're really doing is telling a proverbial boy-meets-girl story dressed in your favorite genre of choice.

And there's where Worldbuilding.SE becomes really valuable

What we do here is help you develop that "genre of choice" infrastructure for your story. And that's why I have to challenge the frame of your question. Because any explanation of how fast or slow, how efficiently or inefficiently, how practically or impractically FTL navigation can be computed is fundamentally irrelevant even if your story depends on the fact — because you're asking how fast something can be done so far in advance of when it would actually be needed to be done that the answer is meaningless, and it's probably meaningless to your story anyway.

Answer 8

I think the idea behind this question is being dismissed far too easily.

For instance, this comment is almost an ad hominem attack:

"After all, in my own (limited) experience, almost all calculations typically fall into one of two categories:"... sorry to inform you, but you are correct. No, not about the complexity of calculations, but about your ignorance thereof. – PcMan

And those answers that have been given seem to miss the point completely and talk about the complexity of the problem, which is not what the question is asking about.

---

Consider an algorithm of complexity O(10ⁿ):

— plot (10^n) - Wolfram|Alpha

Up to about n=6, it will finish relatively quickly; between 6 and 7.5 it will take increasingly longer, and beyond 7.5 it will take a ridiculously long time. (Note that "n" could represent a million data points, not necessarily a small integer.)

The first part of the graph is approximately linear, while the later part of the graph is approximately infinite.

The vast majority of inputs will be in either the first group or the last group: quick to solve or don't even bother trying.

The Travelling Salesman Problem is a common example of something that in general takes impossibly long time to solve. But if it is restricted to small problems, there are algorithms that can solve it quickly.

---

For any given navigation algorithm there will be some minimum number of required input values. It's rather obvious from the above graph that that a solution for any such algorithm will almost always be extremely quick or extremely slow.

If it's in the quick category it can easily be sped up with extra hardware (e.g. if it normally takes an hour, then 100 processors could do it in 36 seconds).

If it's in the slow category, there's nothing that can be done to make it work in a useful length of time.

If there is a practical algorithm for FTL navigation, it would have to be in the quick category, or it wouldn't be practical to use. And I'd say it's almost certain that, as the OP conjectures, it could be made to finish as quickly as desired.

---

In terms of fiction, the flat part could represent calculations of trips of less than 25,000 light-years between endpoints. A single jump across the galaxy would be prohibitive to calculate, but with at most 4 shorter jumps anywhere in the galaxy could be reached.

And perhaps the flat part also requires that the endpoints be near a large mass, such as a star. If this factor is combined with the first limitation, despite being able to quickly jump around within the Milky Way, intergalactic travel would remain impossible.

But wait, what if there are rogue burned-out suns, black holes, etc. floating in deep intergalactic space. Finding them could could provide a series of jumps that could lead to Andromeda. Stepping Stones To The Stars"?

Answer 9

Fourier Transforms and Uncertainty Principle

Assuming you have to measure some spectral properties of the hyperspace medium to make your jump, you'd have to collect data for a certain amount of time to reach a certain accuracy about the current spectral composition. The longer you "listen", the more accurate your representation will be.

In the easiest case, you'd have to determine only a single dominant local hyperspace frequency to sync your jump drive to it. If you sample the hyperspace amplitude for a short amount of time, your uncertainty about it's frequency will be quite large, potentially leading you to set the drive to a sufficiently different frequency to tear the ship apart. The longer you "listen", the safer it will be, and the more smoothly your hyperdrive will operate.

You could choose to listen to the sound of hyperspace all the time, but if doing so comsumes some kind of resource (a large capacitor power drain, degradation of the expensive sensor, exposition to dangers or constant negative effects (gravitational fluctuations, hyperflares, the Warp, ...), ...), it would be necessary to only activate the jump preparation if you actually plan to jump soon.

A more complex relationship between the spectral composition of hyperspace, the planned route and the drive parameters would also involve CPU power as a secondary aspect, and might allow a ship with good CPU/better software to jump slightly earlier (heuristically estimating some parameters with imperfect measurements, leading to similar safety after a shorter time), but that effect would likely be small.

If the mismatch between drive frequency and hyperspace frequency (or a similar metric) caused significant stress to the hyperdrive and/or the ship, you'd get a practical behavior very similar to star wars hyperspace travel: Having to calculate some parameters before being able to jump without just blowing up your drive, more rapid jumps being more risky, and the inability to precompute jumps (changing conditions).

Is this a universal problem domain?

Almost. As long as the jump drive has some parameters that need to be changed depending on "weather" and as long as that "weather" has wave-like properties, there would be a certain minimum measuring time below which safe parameter estimation would not be possible. How long that time is depends on the inaccuracy sensitivity of your drive and the exact nature of that "weather", which ultimately depend on natural constants (+- some engineering factor, which would vanish as the technology matured). In some hypothetical universes that time might be measured in nanoseconds or galactic rotations, but it is entirely reasonable that it might fall in the "10 minutes until we can escape the pirates" range.

The variation of that time across different levels of technology might be relatively complex, but (assuming simple relationships and technology somewhere near physical limits) you'd expect at most a 50% time reduction between a cutting-edge experimental military hyperdrive and an older, but technologically almost mature one.

Could there be a truly universal problem domain?

The only universal necessity of hyperspace-type travel (without any assumptions about its details) is knowing ones destination (in some specific mathmatical description, from direction to fractal parametrization). In principle, a drive could convert you to tachyonic matter traveling in a perfect-vaccuum hyperspace (and back), so at least in some cases knowing direction, distance and speed would be enough. In this case, traveling away from something would almost always be trivial (simply wait for an amount of time guaranteed to land you in interplanetary space, as opposed to inside the core of a star), while traveling close to a target would only need storable/pre-computable sensor data. In practice, it might be necessary to get traffic control information from the target, so hyperspace phone speed might be a limiting factor, but that doesn't apply to fleeing from pirates, so it seems like there are no completely universal problem domains limiting all conceivable forms of hyperspace travel to wait before jumping.

Answer 10

It's not the crunching of the numbers, it's getting them.

To be able to successfully engage a hyperspace jump, you need to know exactly where you are, how much energy is required to enter hyperspace, and how much energy is required to perform the jump.

Requirement #1 is simply Galactic GPS, and anyway, a small error is tolerable.

Requirement #3 is just having good maps and again a small error is tolerable.

The problem is in requirement #2, which depends on the conditions of local space, and these condition vary continuously. All the almost infinite gravitational sources in the Galaxy are moving and rotating and sending off gravity waves, and the resulting noise is what prevents hyper-entry.

To "open a portal" it is therefore necessary to know exactly the hyper-conditions of the local brane with a margin of a few seconds. And, to do this, you need to deploy (disposable) hyper-sensors and map a large enough spherical volume around the ship, and transmit this set of readings (through FTL) to the computer. Being transmitted FTL, these readings describe the "future" conditions from the point of view of the ship, and can be used to calculate the exact conditions at the future time of the scheduled jump.

The accuracy of the readings is proportional to the time covered by the reading themselves, usually several seconds (or as many as you need). Since the ship and the sensors themselves influence the readings, and do so with their own gravity waves that travel at the speed of light, there is no way of reducing this "settle time".

Usually, furthermore, a little more time is required to have a margin allowing FTL recovery of the sensors, which aren't cheap (you can cut that time by abandoning the sensors).

In an extreme emergency, you can deploy the sensors nearer to the ship, and use shorter readings to calculate a rough estimate for the hyper-entry. The rougher the estimate, the higher the risk of a catastrophic entry, with the ship hypering as a discrete collection of chunks.

Answer 11

It's completely arbitrary and as an author/world-builder you can add whatever simplifications you like. I'm a technical developer with roughly engineering math education & a bit more interest.

I think it's more useful to relate time complexity to factors that make your in-universe decision making interestingly variable.

1. Risk - probability of a successful jump. That implies you may be up against a culture that accepts a higher risk for strategic advantage, out of desperation or warrior culture. David Weber explores this with relation to wormhole transitions, in his Stars at war series, especially Shiva option.
2. Accuracy - related to risk (you may end up in a star) but consider starting point/vector, ending & desired accuracy. You could build in an exponentially increasing requirement for accurate calculation up to a threshold where galactic movement limits it. You can blindly jump at almost any time (although gravity well restrictions are a common trope).
3. Physics of observation. This gets more to a realistic physics/maths limit. Assuming you have jumped into a system, you need to get light-speed limited information back on gravity bodies, other factors. Very old industrialised systems would have patterns of satellites feeding this info from closer range. Think of this like we can use localised GPS from ground transponders to supplement orbiting locations, for millimetre accuracy.

Answer 12

An analogy:

As the hardware capabilities of computers improves, the software running on them grows more hungry for the increased capabilities. The operating system for the latest hardware will run much slower on older hardware. So people tend to get a few OS upgrades and then eventually see the need to update their hardware as well to keep it running smoothly.

Likewise, given the latest hardware capabilities, navicomputer software developers write FTL calculation algorithms that max out processing capacity of the system to achieve the calculation within a reasonable amount of time (say, 30 seconds). Let's say this puts the chance of catastrophic failure in an FTL jump at, on average, 0.02%.

A few years later, more advanced hardware is available, and the software devs now are able to refine and add additional features to their computation software which, while keeping the time-to-calculate within a reasonable number of seconds, bring the chance of failure down to an average of 0.0185%. This is a reasonable enough improvement in safety that over the next few years the adoption by ship owners of the newer hardware and software follows a standard S-curve (some early adopters, most middling, some late).

Some cargo vessels may choose to upgrade the software only, and suffer an increase in calc time from 30s to 1.5 minutes. But the tradeoff seems worth it to some. Some smugglers keep running the older software, but upgrade the hardware so they can calculate jumps in only 24 seconds.

Thus, the "optimize it to death" may well look like how hardware and software progress look to us, and produce similar results to what we see in the real world. It goes slowly over time, and often we marvel at what the techies can accomplish, while also lamenting "why is it so hard to just make X system do Y?". It's messy, but we can have nice things. (That is, nice things that still have some time cost, as opposed to the only options being things that are either near instantaneous or unusably slow.)

Answer 13

Several things come to mind

1. N-body problem. There is no good fast solution for it as of now, basically you need to simulate, which might be a very painful experience if your n is the whole galaxy.
2. If you are numerically solving the differential equations that describe both very small and fast objects (your FTL ship) and slow and large (the galaxy), a fun little problem can arise: https://en.wikipedia.org/wiki/Stiff_equation. Which makes it a real pain to solve fast.
3. Something very simple, like having to calculate elliptic integrals in large numbers and very precisely. Since everything moves more or less along ellipses according to the Kepler laws, I won't be surprised if an elliptic integral appears somewhere. And that is not even considering relativity, the quantum mechanics and all the FTL science.

Answer 14

Frameshift:

Nothing in your problem statement precludes precalculating the answer. Ok, you need to know your jump point--but can you not simply go to the point you did your calculations for? To some extent you must do that anyway as I can't recall any of the major systems that require you to stop before making your jump. (Some books do, however--but those always involve transit over fixed links, you just need to approach the link carefully.)

Thus we need to take a different approach: Consider what happens with the GPS system. It inherently takes at least 30 seconds to get a GPS fix because you must download the weather report which describes the propagation delays which are to be expected.

Therefore: Hyperspace isn't flat, it has waves. Ideally, you download a report on the waves from navigation satellites which maintain updated reports out as far as one can jump, but hyper-capable ships also have a sensor that can gather the information, albeit with less precision.

The on-board sensor is simply a point reading and can't actually see the waves, they can only be determined by seeing how the reading changes over time. (Picture a pole in the ocean with a float that goes up and down and you can only read where the float is.) Getting the wave state reasonably correct is vital as it bends your course as you enter hyperspace. (Picture what happens to a reflection in the water when there are ripples.)

Thus normal shipping simply reads the navigation satellites and makes their jump. However, when you're trying to operate without the permission of the authorities (I can't think of a scene where hyperspace calculation time mattered that didn't involve illicit operations) this isn't an option, you have to make your own measurements--note that it's not actual CPU time involved and thus you can't speed it up by throwing a bigger CPU at it.

Yes, you can make a hyper jump blind--but if you do so where you arrive is wildly unpredictable, you very well might wind up so far away from home you can't find your way back.

Answer 15

The calculation can be polynomial, take time, and not be improvable

Getting through space

To get through space you just need to calculate f(t), based on g(t), for the trip at various natural number values of t from 0 to N. The value N increases with distance. The local space folding energy at every value t is e(t). An incorrect answer with much energy leaves your ship ripped apart, too little and it collapses on itself.

If g(t-1) > e(t) : g(t) = g(t-1)-e(t)

If g(t-1) < e(t) : g(t) = g(t-1)+e(t)

f(t) = g(t)+g(N)

Essentially there is the energy needed by the tunnel determined by the end point, and the energy needed due to local fluctuations.

limits of parallel computing

So computers could do this in parallel right? It is just adding. Well, since every answer depends on computing the last value before we know any answer we need to wait on that computation to get the answer. However, the branching behavior makes it impossible to calculate the last value in parallel. Now it doesn't mater how many cores you have, you can't compute this faster than O(N).

Making it take time

You are moving faster than light and the effect of space folding might be very strong. Maybe you only need to run this algorithm for every kilometer, or maybe it is every meter, or millimeter. The greater the required accuracy, the greater the maximum value of t over the same space. Even the fastest adders and comparers still take non-zero time to run. Once you make the smallest component moves at light speed and you can't speed up anything you will not be able to compute this faster. once it is discovered it might be in every ship, but it still takes the same amount of time.

Answer 16

Aircraft flight planning takes time

What I suggest as a good analogy (and perhaps the source of the trope?) is flight planning for an aircraft. Pilots are required to familiarize themselves with a bunch of information that is both required by regulation and necessary for the safe operation of the aircraft. Depending on the type of flight (general aviation, airline operation, military) and other characteristics the details will vary. The FAA has an Advisory Circular titled "Pilot's guide to a Preflight Briefing" that explains some of the information required and the process.
The preflight planning process is not currently computationally limited, but instead is essentially data source and human limited. If you are planning a flight for a long distance your weather briefing has to include weather forecasts for many hours in advance along the whole route of flight. It also has to include state information (airport landing procedure availability, etc), for your destination and the whole route of flight. The planning includes winds, visibility, icing conditions, navigational equipment outages etc.
A pilot needs to gather the appropriate information, decide a route, perhaps gather more information, then perhaps do some calculations. The calculations themselves are not computationally intensive (ie fuel to climb to a chosen altitude at the current aircraft weight, temperature and winds), and they could even be done with simulations fairly quickly. But, the process takes some time.
Some of this source information, from a pilot perspective, comes from sources that are computationally intensive to generate. Weather simulations to generate forecasts are one of the historical and ongoing uses of supercomputers.
Pilots will then update their flight planning as the flight progresses (ie winds are higher, so choose a different altitude etc). The autopilot on an airplane will adjust for some local information (a local updraft, so descend to desired altitude) but they need to have a current "understanding" of the environment. In some sci-fi while in hyperspace information is cut off, so it would not be possible to adjust for changes in gravity etc in real-time. Those flight details would have to be planned out beforehand. If the environment can change (stars move, planets move, solar storms, space stations move etc) then there is a lot of information that has to be gathered or simulated.
If it is necessary to plan your way around hyperspace, it seems reasonable that it would be necessary for the pilot, and the onboard computer, to have a good data set to do that planning. Gathering that information and synthesizing a good plan would involve scans, simulations, and communications with other data sources. It seems very reasonable to me that a hyperspace jump is at least as complicated and a flight current flight plan, and would take a similar amount of time.

Answer 17

There are some great answers here, but here's another.

An FTL calculation is like calculating the detail in a fractal, the more resolution you want in the fractal, the longer the calculation takes. With FTL a high resolution gives you a greater chance of making a successful jump.

Space liners carrying many thousands of passengers will calculate jumps to 99.999% resolution, each 9 increases the likely hood of the ship arriving at the destination in one piece and not diffusely smeared across several light-years worth of vacuum.

A scam artist who's shields are down and is about to be annihilated by a gangsters turbo-laser shot might take the risk and jump at 90% resolution (anything lower than 90% is certain death), opting for near certain death as opposed to actual certain death.

The inputs for the calculation are distance, direction and the conditions of your local space eg. density of the vacuum and amount of vacuum energy (maybe the further one is away from a gravity well the easier it is to calculate).

Readings are taken every x nano seconds and plugged into the fractal like calculation, it can take y actual seconds (or minutes/hours depending on what your plot demands) for the results to converge on a given value, i.e. the final result of z%.

There are jump points and destinations where the local conditions are known to always calculate a jump with safety factor so high it's essentially 100%, these are well worn trade routes and hyper lanes.

A smuggler on the run (carrying only a kid and an old guy), who values his skin might well risk Imperial turbo-lasers for another second or two to get his FTL calculation up above 98%.

Answer 18

There are a lot of physics-y problems that take a long time to compute, but not prohibitively long.

In college, I worked as a programming assistant for computational chemistry research projects. These calculations often required several hours of computation, sometimes even overnight- and this is on systems in the neighborhood of 24 cores with 64GiB of memory. Now these run a lot faster on GPUs, but still, there are an enormous amount of expensive computations that go into this. Atoms and molecules are really complicated in how they interact and there aren't any closed forms of the equations that go into these calculations, so most of these use gradient descent iteration using compositions of gaussian functions to approximate electron orbital wave functions. Spacetime at the astronomical scale is about as complicated as the quantum world of atoms thanks to relativity and gravity.

It's entirely plausible that the mathematics required to make a sufficiently precise hyperspace jump do not have a closed form and therefore require iterative approximation. On top of that, the calculations must account for hundreds to millions of celestial bodies (mostly planets, moons, and stars; however asteroids, satellites, and debris may need to be accounted for in some cases) near the jump destination because of how they warp spacetime with their gravitational fields. Right there, you have an iterative calculation built on a $O(n^2)$ calculation of complicated equations, which may be iterative themselves. Although you can probably parallelize all the celestial forces on GPU-like architecture, you are still bound by a sequential bottleneck on the iteration. On top of that, such calculations might involve a number of randomized guesses in order to avoid local optimums, meaning it may iterate on a few hundred guesses until it's pretty sure that the solution has been reached with sufficient precision.

The end result is a hyperspace jump that takes several minutes to hours to calculate, depending on how many significant celestial bodies are involved and how many guesses it takes to reach the global optimum.

On top of that, since the celestial bodies which affect the jump are always moving, these jumps cannot be pre-calculated. Additionally, the jumping spacecraft must account for its own position and momentum, so each spacecraft needs to do its own calculations.

What's interesting is that you could conceivably take a "risky" jump before the calculations are completely ready, but this could potentially land you a few lightyears off course, where your STL impulse engines are useless. This is great for quick getaways, provided you have enough Hyperjump fuel for another properly-calculated jump after that, but this isn't going to cut it when pursuing another spacecraft.

Answer 19

FTL calculations involve a simulation, or a simple calculation.

In Star Wars, you navigate by traveling down hyperspace lanes, dodging the mass shadows of heavy objects. It makes sense it would take an arbitrary amount of time to calculate stuff, because they need to map out a route through a complex environment. There's many possible solutions for how they could fly, and changing and complicated situations from moment to moment.

In Battlestar Galactica, they don't have good computer. They have an old ship with old data, and the cylons are much better at jumping. It makes sense they would take ages to calculate jumps, because they lack super computers. When the rebel basestar offers to join them, their modifications they offer would massively improve their jumps.

Some universes just have fast travel.

Take Star Trek for example. They can just go to warp on a whim. This is because they don't need to calculate routes, they just fly through the universe in a subspace bubble. They can react to local threats on the fly.

So, decide what sort of ftl your universe has- it might be a simulation, and so can have arbitrary complexity based on what you need to simulate (made easier by known routes, or better data) it could be a simple calculation fast computers could make easier, or it could be you just move fast through space and need no calculation time.

Answer 20

I was going to comment on n-body but see that Wotan has done so.

Various people havecommented on predictions based on obstacles in or near the "flight path", but these would need a super-luminal pre-flight ability to detect.

Instead posit that the ability to launch depends on the ability to calculate local n-body constraints out to a certain level of precision.

• Objects like in-system planets or the local star have minimal effect die to inverse squared (or some other) law, and/or they are advance predictable.

• Any local "ships" or bodies have greater effects and if their actions are not controllable, anything that deiates much from a gravity constrained curve or constant acceleration would need to be factored in at the time.

• It could be found that very small particles (dust, gas clouds) at very close proximity have a significant effect and need to be included in the n-body calculation.

None of the above depends on the type of FTL used - it is a calculation necssarey to determine the appropriate parameters for making the "jump to light speed".

Answer 21

It is all about the insurance...

Calculating the flight-path involves a certain risk. In an infinite universe there are infinite flight-paths possible. The trick is to find those paths that get you from A to B and don't get you (or others) killed.
Not getting killed is not guaranteed. (Solving that would be a NP problem.) The best you can do in reasonable computing time is to find a solution with acceptable risk.

As computers get more powerful it becomes a trade-off:

• Faster calculation with the same risk.
• Same calculation time, but finding a solution with less risk.

Insurance companies don't like risk for obvious reasons. It really hurts their bottom line if they have to pay life-insurance for half the population of a planet if some space-cowboy jumped his freighter to the planets surface in stead of to parking-orbit. (And don't even mention all the material damage.)

However the Galaxies insurance companies are quite wealthy businesses which have enough political and economical influence to do something about that.
They managed to push all inter-stellar governments into drawing legislation that mandates that any improvements into computing capability must be put towards making jumps safer by reducing the risk. And to make any navigation computer that doesn't play by these rules illegal in their jurisdiction.

That still leaves some cowboys, at the fringes of the known Galaxy, without these safe-guards that can calculate less-safe jumps faster, but they don't matter much. They can't get insurance themselves anyway.
And the insurance companies categorically refuse to pay out any damages when they cause damage. They simply state "That this accident could happen is due to unregulated navicomps being used. Your government should have enforced the rules. We are not liable. Talk to your government for compensation."

Answer 22

This answer is a slight alteration on Nullius in Verba's answer.

Assuming you have to check the entire flight path for objects greater than a few centimeters, there is a nontrivial integration time needed for a telescope (or other sensors) to be able to "see" all the objects along the trajectory. Note that this telescope would have to be many orders of magnitude more sensitive than our current telescopes to be able to accomplish the task in a reasonable amount of time.

As other answers have said, it's not about crunching the data, it's about acquiring the data.

Answer 23

Polynomial time is fast in theory, but it depends on two things in practice:

1. The size of the input
2. The degree of the polynomial

Both of these are things you have to play with to make this premise work.

As to the size of the input, we'd really only need to consider anything of sizable gravitational impact. Every subatomic particle between here and there gets you rapidly into the realm of computationally impossible. Everything dwarf-planet and larger can get you a nice couple thousand objects for reasonable length jumps. Now all we need to hit the timings you're looking for is a high degree polynomial time algorithm.

Let's take a real world potentially relevant algorithm: Parzen Windowing. This is trying to find clusters of points by summing probability distributions (such as gaussians) around each point and using hill-climbing to find the peaks. This could be relevant to hyperspace because you need to determine which physical bodies are linked in the hyperplane so that you can properly determine the distortion they will have on your journey through the void.

Parzen Windowing is a polynomial time algorithm, but the degree of the polynomial scales with the dimensionality of your data. Depending on the implementation, the complexity can be one polynomial degree higher than your number of dimensions. So, trying to do Parzen Windowing on 3-dimensional data (objects in space), you've got yourself a quartic time algorithm, i.e. O(N⁴). This is going to be slow even for moderate values of N (like a few thousand). There are a lot of shortcuts you can to do speed it up but all cause a loss of accuracy.

The tradeoff between speed and accuracy is key and likely always present. Consider smaller objects and your result will be more accurate but N goes up. Use more approximation to reduce the polynomial complexity and your runtime goes down as does your accuracy. This is actually mentioned in a major Sci-Fi property: in Battlestar Galactica, Helena Cain performs a blind jump (a dangerous FTL jump performed without pre-computation to random coordinates) to get out of a bad situation.

Whether or not blind jumps are possible will depend on your FTL system. If it's about just computing space coordinates, jumping to a random location is 99.9999+% safe. Han Solo doesn't even know what a parsec is, so why would you trust his explanation about FTL? The real risk of poorly computed FTL, especially if you are using some sort of space-tunneling mechanism, isn't getting there, it's getting back.

If you end up somewhere totally outside of mapped space, you may have no way back as you need to know enough about the objects between your source and destination to plot it accurately. Now you have to get back before you run out of food/fuel. But even moderate inaccuracy can waste plenty of time and fuel trying to correct, especially if FTL jumps are fuel intensive (if it's not, just do a tiny FTL jump to correct). As a result, it would make sense for routine (i.e. non-emergency) jumps to involve a large degree of computation. This also may be more important when multiple ships are involved as you want them to get to the same destination.

The result of all of this is the following:

• Spend a bunch of time (several hours) calculating and you can end up within a few thousand kilometers of the target, but if you get unlucky, you could end up a million kilometers away (takes a few days at sublight speed to correct); more computation time can reduce this risk for correctness critical jumps, but spending a day of computation to save a small chance of several days of transit is only worth it for correctness critical jumps or for stations computing coordinates for common hyperspace routes.
• Shave some time on your calculations (do them in 20 minutes) and you end up within an Astronomical unit of the target and need to spend some fuel (which is expensive) and maybe a few days at sublight speed or another FTL jump to correct.
• Do rushed calculations (5 minutes) and you probably end up within a light year of the target and need another (presumably smaller but still expensive) FTL jump to get there. There's also a 1% risk you are lost forever in space and will run out of fuel before you reach civilization.
• Blind jump (20 seconds to get to minimum viable coordinates). You end up somewhere; 10% chance you're lost forever in space and will run out of fuel before you reach civilization.

Could specialized hardware improve on these numbers? Sure. Make that part of the plot. The Millenium Falcon is "better at hyperspace", and according to the movie "Solo", it's because it has a better hyperspace computing device [spoiler alert].

Answer 24

I’m a computer programmer, and it’s quite common to have processes that take from fractions of a second to hours.

These aren’t a single equation, but a series of data looks ups and calculations on the result. Given that you are traveling in space, it’s likely that part of what you are going to be doing is developing a good model of your position and environment. A count-down is feasible as percent done background task, maybe not super accurate, but does it need to be? Or perhaps that could be a plot point, it gives 30seconds left and jumps early, says it’s done and then jumps 5 seconds later.

Answer 25

You can make the calculations take as long as you want by saying there is no exact "solution". Instead there is only an approximation that a pilot can deem "close enough."

For example, it could be that the hyperjump solution must be arrived at by simulating the jump based upon known values (gravity strengths and distances, perhaps). The result would be the locations and probabilities where the ship might end up. Slightly altering the hyperdrive's inputs can yield wildly different results. (Inputs could include the mass of the ship, starting vectors, starting velocity, how much power is dumped into the hyperdrive, etc.)

A bad solution could spray the ship all over a solar system. Or land it inside a star. Or yield a near-infinite number of places where the ship would end up, each with an approximate equal probability.

Answer 26

Optimization in a Highly Nonlinear Space

Optimization problems can take any amount of time, so they're an excellent tool to use here. The trick to optimization is that typically the actual problem is NP-hard, but it can be approximated using P algorithms. The more CPU time you're willing to spend, the closer the approximation gets to the ideal answer of the NP-hard problem.

In many real life physics situations, a system can be described as a set of non-linear differential equations. Given a current state and a desired state, you can compute the optimal path. Given a sufficiently tortured set of dynamics equations, you may find that there are very thin paths with acceptable costs, surrounded by vast pits where the costs are completely unacceptable. Finding a solution for a path through such a system can be extremely expensive.

They can also be very initial state dependent. Drawing from a real life project I worked on, you could have your FTL computers constantly calculating plans to get from point A to point B, where point A is somewhere nearby and point B is far away. When it's time to jump, you resolve the problem for your exact point A', seeded by your most recent plan. There are many optimizers which perform much better if given a nearby point.

Also remember that a jump can be more than just one impulse. It can be an entire dynamic solution for the time the vessel is in hyperspace. Needless to say, this dramatically increases the state space for this optimization problem, increasing the difficulty as much as you like.

Answer 27

The problem isn't calculation, but verifying that the path acknowledges that they've "saved" a timeslot to avoid traffic accidents.

As a bit close to a frame challenge perhaps, but there may not be as much of a problem with the mathematical computation on the ship computer itself - figuring out how to make the jump safely with other ships also making jumps along the same path, and not colliding with them at FTL speeds is where the complexity gates the time needed to make an FTL jump.

Admittedly, this is taking a bit of inspiration from Guardians of the Galaxy Vol.2, another space story that used portal jumping to achieve "FTL" without necessarily just moving at faster than light speeds, but the same basic principle could be applied to Star Wars style hyperdrives and their claim of not being as easy to just jump, and could explain why a Star Destroyer takes as long as the Millennium Falcon to make an FTL jump, and even with knowing where the destination using hyperspace tracking, they couldn't necessarily just get to a location before another ship in FTL.

So, what the ship computer would be relying on isn't their computer, but their computer's ability to send a request to other relay computers and verify that they can make a jump to a location safely and use it to jump to another, potentially pre-mapped location, at a specific FTL speed (Say, 1.25c instead of 1.5c, or 2.5c, depending on what their ship can accelerate/decelerate to.).

Said relays would likely have a ledger of public timings for ships to ensure that they don't conflict- possibly involving ship sizes so that they can know how much efficiency they can stick in with ships, and check if they can safely leave hyperspace without crashing into another ship that was leaving the same gate and slowing down first -, and confirm a specific timeslot or deny a specific timeslot requested of the ship that was attempting hyperspace travel.

Admittedly, a portal/relay explanation does run pretty close to violating:

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

But these same calculations could still be applied to Star Wars style hyperspace jumps, especially as occasionally ships have, in Star Wars, gone through hyperspace in formation. So at least some confirmation of when to enter and where to go in from and how to exit safely would have to be confirmed, as you wouldn't want to go faster than the ship directly in front of you, even if, hypothetically, your ship could go through FTL faster.

That may require communication with other ships, however, and the relay/portal jumping system would allow a ship to not necessarily broadcast where they were going to enemy ships along the way, without also conflicting with them.

It also allows for a possible example of a greater way to scale up the transactions necessary to allow for FTL allowing for variance in how long it takes for a ship to get to FTL...

The timeframe of calculating a safe travel timeframe and ensuring a lack of collisions might be effectively enforced by a ledger verification system like a Blockchain

Ultimately, this relays would likely want to have a way of enforcing that nobody breaks the rules they've setup in terms of timeframes available and try to jump in when another ship is also taking the exact same space in FTL-capacity.

Given that these relays are likely automated for their traffic levels and not resolved like modern aircraft going over the North Atlantic, and the need to manage a lot more relays that possibly can be brought into the same connection, you'd want to represent the timeframes in a way that makes the most use of the time they have, leaving gaps for anyone making an impromptu jump and hopefully resolving their issue quicker.

As a result, a variety of ship computers might be requested to perform actions, or a variety of relay specific computers might be required to do this instead, of a set of blockchain related transactions on the timeframe they're moving through, and which relays to move from once getting to the next one.

The amount of blockchain transaction blocks needed to ensure a ledger is both up to date and accurate to prevent travel conflicts, could be what causes a significant amount of time - giving the shipboard computer possibly only as much as a router IP address way of indicating where they want to go, and letting the rest of the relay network determine how they actually get there. and when they'll arrive and depart each relay such that it is smoothly done.

Or in short, hyperspace traffic is the cause of why it takes so long to calculate a route, given that you can't recalculate mid-travel at the FTL speeds involved.

---

Answer 28

A Topical Example Using the Einstein Field Equations (EFE)

So, the EFE is $R_{ab} - {1\over2}Rg_{ab} = {{8 \pi G}\over c^4}T_{ab}$

Looks pretty simple, doesn't it? But it isn't.

$g_{ab}$ is your starting point in this oversimplified nightmare. It is an expression of your co-ordinate system. It can be 3-dimensions of space + 1 of time (the usual 3+1 = 4D), something simpler, or (for computing higher dimensions (such as "hyperspace") more complex.

$R_{ab}$ is your second derivative of $g_{ab}$, relative to evey element of $g_{ab}$. So, this is $\delta x \delta t \delta t$, but it is also $\delta x \delta y \delta z$ and $\delta y \delta z \delta z$. All said, there are $N^3$ equations for any given $g_{ab}$, where N is the number of dimensions (4 for 3D of space + 1 of time) = 64 equations.

Many of these 64 equations are pre-dumped when doing this by hand, assuming certain values will be zero, constant, or duplicates of others. But we're trying to figure out how big the calculation can be, so let's not skip anything.

R is a product of $R_{ab}$, $T_{ab}$ is your stress-energy tensor, and may be the space-warping ship engine output that you are trying to calculate, although other massive and energetic bodies are contributing to this stress-energy. G is assumed to be constant, but might not be.

Once you have calculated this equation for a single collection of points you may then compute the geodesic (the basic equations of gravitational motion).

Each equation has at least one "body" or "component" contributing terms to it (that's not entirely true, the zero-body solution is equal to zero, but that's not useful for anything). Each "component" may contribute as few as one terms (n = 1), or as many as n = $N^3$

Let's Scale This Up To Known Concerns

If string theory is correct that there are 10 dimensions of space + 1 of time, and assuming for a your hyperspace calculation that you can neglect none of these.

That's N = 11, $N^3$ = 1,331 equations of various properties that you are looking up in your almanac or sensor feeds before you can compute an engine burn.

So, let's say you're jumping to orbit:

• You need to worry about the sun, earth, and the moon (3 bodies) : you have $N^3 [3 n^3] = 3N^6$ (or 5.314 million) calculations that you will need to perform.

But let's say solar wind is a big contribution to navigational error in hyperspace, and you need to re-calculate at say every thousand kilometers between here and the moon (400,000 kilometers away). You'll have about 2.1 billion calculations total. Not so bad for a modern computer.

But let's say you're going from Earth to Mars : 3 more bodies to worry about (Mars and it's two moons), and 2.1 billion kilometers of distance at the closest approach between Earth and Mars (five times that at the greatest distance between Earth and Mars, which would pass through the paths of Venus and Mercury). $6N^6 \times 2.1$ million = 22 trillion calculations. Which would take 372 minutes on a modern 1 gigaHertz processor.

Imagine the not-best-case approach to Mars past Venus and Mercury : $8N^6 \times 10$ million = 141 trillion calculations, taking 39 hours on a modern computer (you'd need a faster future-tech computer to do this kind of calculation on the fly).

This might also explain why, in these sci-fi scenarios, hitting your destination accurately is usually something of a surprise : you are neglecting all sorts of things like space dust, smaller rocks, and other vessels, just to compute this thing in a timely manner. The calculation has a lot of error in it, because you are knowingly ignoring a lot of things that contribute to the answer, just so that you can get any answer at all in a timely fashion.

It might also explain why, in some of the sci-fi scenarios that use this idea that "high precision" jumps (into a planet's atmosphere, for example, or "too close" to the planet at all) are considered by most professionals in-universe to be suicidal. It is.

Answer 29

FTL works like a transporter

And let's be realistic: the FTL calculation is not going to include actually transcoding a video, because that is obviously irrelevant to travel.

Actually, transcoding could be exactly what your ship is doing! Normal matter is restricted by the speed of light; so, in order to exceed the speed of light, you may need to become something else entirely... So, what your ship does is it accounts for every atom on your ship and translates it into a data stream of FTL energy which then reassembles back into normal matter somewhere else much like a Star Trek style transporter.

But before your ship can do this, it needs to scan its entire self and transcode that into an exact data stream. You can not pre-calculate this because the exact composition and layout of your ship and the things on it changes moment to moment as people walk around and do things. If you were to say for example scan your ship 3 weeks in advance, then all that cargo you picked up last week would disappear, and everyone would forget what they spent the last 3 weeks doing because you are basically "using an old save file". But to make matters worse, if you used a calculation that assumes something exists that is no longer there, then you will not have enough matter to fully translate into an FTL data stream; so, you might come out the other side missing something else that needed to be reassembled from the same mass; so, congratulations, you just topped off your fuel supply as per the old copy of your ship, but your data stream did not contain enough mass to reassemble the left half of your captain's body.

So, it is not the flight path that takes a long time to calculate but the exact state of your ship at the moment of activating your jump drive. You take a "snap shot" of your ship very quickly, but then spend minutes or so transcoding that snapshot into a data stream.

So, how does this ensure the calculation takes a human scale amount of time?

Ray Butterworth's Answer does a GREAT job of explaining why there is such a narrow window between a ridiculously long and short calculation when the calculations scale exponentially as per a traveling salesman or multi-body problem type problem. But transcoding follows a different set of rules. The actual math behind video transcoding is very simple to the point that a single operation can be measured in the billionths of a second, but it takes a long time anyway because the process contains trillions of operations that need to happen.

Your transporter follows the same logic. You ship begins by taking a molecular snapshot of the whole ship... let's say we are looking at a 10,000 ton destroyer.

If we assume an average molar mass of about 45 g/mol we can say that your ship contains about 1.34e32 molecules that that need to be converted into some manner of data-point. Using modern computers this would take a stupidly long time and need a computer much more massive than your ship itself, but we are not talking about modern computers. If your civilization has learned to pack data into the false vacuum of space or into the as of yet undiscovered sub-atomic particles that make up all other subatomic particles, then you may be able to store and process vast amounts of data in a single atom. Since the only thing your ship does at this scale is wardrive buffering, it means you can scan at the atomic scale and only loose your warp buffer when you jump. If we can assume these specialized warp buffer computers are about ~20 orders of magnitude better than what we have today, then running this transcoding operation would feel a lot like rendering a video file does to us.

The reason this scales well for your setting is that its complexity has a linear relationship to the size of your ship. So the calculations for a 10,000 ton ship are only 5 times as complex as for a 2,000 ton ship. So, in this respect you can not just keep adding computers until the calculation becomes arbitrarily short, because the faster you want the transcoding to happen, the higher percentage of your ship you need to dedicate to computing power. So, while it is not exactly the same as transcoding video files, it will follow more or less the same principles. You just need to match your setting's computational technology to the general wait time your plot requires.